Swapping Nodes on a single linked list

Question

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 << current->number << endl;
}

EDIT: I now have this as my swap part, but it still doesnt seem to work correctly

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

EDIT2: This one doesnt seem to work either, I get a seg fault.

    //swap previous's->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;

Answer 1

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 Node4->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 second->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?

Answer 2

In most real-life scenarios, swapping the values will be the best solution:

void swapNode(call * &head, call * &first, call * &second) {
    // swap values, assuming the payload is an int:
    int tempValue = first->value;
    first->value = second->value;
    second->value = tempValue;
}

If that's not allowed, then you want to do a similar-style swap on the ->next instead of the ->value component. And then do another swap on the firstPrev->next and secondPrev->next components. Watch out for the special case where first or second == head.

Answer 3

While I am not 100% sure the answer should involve references to node pointer (or pointers to pointers) and this should then handle a case when one of the nodes is the head of list as well.

void swapNodes(node *&first, node *&second)
{
  node *t = second->next;
  second->next = first->next;
  first->next = t;
  t = second;
  second = first;
  first = t;
}

Then you can call it for example:

swapNodes(head, secPrev->next);

or

swapNodes(firstPrev->next, head);

or

swapNodes(firstPrev->next, secPrev->next)

and it should work automagically.

EDIT:

swapNodes could be even more readable:

void swapNodes(node *&first, node *&second)
{
  std::swap(first->next, second->next);
  std::swap(first, second);
}