Swapping Nodes on a single linked list

Question

I am trying to make a `swapNode` function that can take any two nodes and swap them. I've made an algorithm that works if they're at least 2 nodes away, but I can't seem to come up with an algorithm that will work if they are closer to each other. Here's what I wrote so far: ``` void swapNode(call * &head, call * &first, call * &second){ call * firstPrev = NULL; call * secPrev = NULL; call * current = head; //set previous for first while((current->next != first) ){ current = current->next; } firstPrev = current; current = head; //set previous for second while((current->next != second) ){ current = current->next; } secPrev = current; current = second->next; //set firstPrev-> next to second firstPrev->next = second; //set secPrev->next to first secPrev->next = first; //set second->next = first->next second->next = first->next; //set first->next to current first->next = current; current = head; while(current->next != NULL){ cout << current->number << endl; current = current->next; } cout…

Accepted Answer

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 `next`s of the two previous ones, and then swap the `next`s 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?

Swapping Nodes on a single linked list

Solution

Problem