Swapping Nodes on a single linked list

by

Say we have:

Node1 -> Node2 -> Node3 -> Node4 -> Node5

To swap two nodes, you need to swap the next values of the ones before each of them, and also the next values of the nodes you want to swap.

So to swap, say, Node2 and Node3, you effectively have to swap Node1->next with Node2->next, and Node2->next with Node3->next. That will work, even if they’re right next to each other (or even if it’s the same node). For example:

Swap Node1->next and Node2->next

Node1->next = Node3
Node2->next = Node2

Swap Node2->next with Node3->next

Node2->next = Node4
Node3->next = Node2

This comes out as:

Node1 -> Node3 -> Node2 -> Node4 -> Node5

Swapped!

As unwind noted in the comments section, if swapping Node1 with anything, you’ll have to set a new head for the linked list.

In response to the edit of the question:

Your code for swapping almost right. However, you need to swap the firstPrev with secPrev. It just so happened in my example that we were swapping one of the node’s next values twice, because they were next to each other. But logically, we want to swap the nexts of the two previous ones, and then swap the nexts of the actual nodes. Try this:

//swap firstPrev-> next with secPrev->next
tmp = firstPrev->next;
secPrev->next = firstPrev->next;
secPrev->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;

If you’re getting a segfault, check the tmp variable – it could be an error of allocation or deletion somewhere. Where do you get the segfault?

More Related Contents:

  1. CPP- I am getting Segmentation fault (core dumped)?
  2. How to recognize the meaning of a linked list function in c++ [closed]
  3. swap string a in place to string b in C++ [closed]
  4. I wrote this method to delete duplicate elements of a linked list, but it shows segmentation fault, why? [closed]
  5. What can I do with a moved-from object?
  6. How do I properly delete nodes of linked list in C++
  7. Examples of when a bitwise swap() is a bad idea?
  8. how to provide a swap function for my class?
  9. Relative performance of std::vector vs. std::list vs. std::slist?
  10. Bjarne Stroustrup says we must avoid linked lists
  11. How does the standard library implement std::swap?
  12. adding list items or nodes in linked list
  13. Create a reverse LinkedList in C++ from a given LinkedList
  14. How to sort a linked list using bubble-sort?
  15. Why do linked lists use pointers instead of storing nodes inside of nodes
  16. iter_swap() versus swap() — what’s the difference?
  17. Does C++11 change the behavior of explicitly calling std::swap to ensure ADL-located swap’s are found, like boost::swap?
  18. Move semantics == custom swap function obsolete?
  19. C++ trying to swap values in a vector
  20. Is a Linked-List implementation without using pointers possible or not?
  21. A confusing detail about the Most Vexing Parse
  22. Two different values at the same memory address
  23. What are the differences between struct and class in C++?
  24. Difference between iostream and iostream.h
  25. What destructors are run when the constructor throws an exception?
  26. `auto` specifier type deduction for references
  27. TMP: how to generalize a Cartesian Product of Vectors?
  28. Check double variable if it contains an integer, and not floating point
  29. How to tame the Windows headers (useful defines)?
  30. How to get file extension from string in C++

Leave a Comment