Pairwise swapping of elements in a linked list (by changing pointers)

Question

The problem statement is the following:

Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5->6->7 then the function should change it to 2->1->4->3->6->5->7, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5

Here is my solution:

void swapPairs(Node* head) {
    if (!head->next || !head)return head;
    Node* current = head->next;
    Node*prev = head;

    while (true) {
        Node* next = current->next;
        current->next = prev;
        if (!next || !next->next) {
            prev->next = next;
            break;
        }

        prev->next = next->next;
        prev = next;
        current = prev->next;   
    }
}

The issue with the solution is that when it gets to the end of the function, the head no longer points to the beginning of the list since both current and prev have been moved. I've seen other solutions online which do the same thing as I'm doing here, but maybe since they are implemented in C instead of C++, there is some aspect of their code that allows for the head to remain pointing to the start of the list.

I realize that this is probably a really simple issue to solve, but I'm just not currently seeing the solution. What would be the best way to maintain the beginning of the list throughout the algorithm?

Answer 1

You can keep a pointer to the new head at the beginning of the function and update the head at the end of the function with that. Note that I changed the argument from Node* to Node ** because we want to update the pointer value so that when we update head, we write to the same memory location that passed to this function. As a result, the correct value of head will be available in the caller of this function when we return from it.

void swapPairs(Node **head) {
  if (!(*head)->next || !(*head))
    return;
  Node *new_head = (*head)->next;    // the new_head
  Node *current = (*head)->next;
  Node *prev = (*head);

  while (true) {
    Node *next = current->next;
    current->next = prev;
    if (!next || !next->next) {
        prev->next = next;
        break;
    }

    prev->next = next->next;
    prev = next;
    current = prev->next;   
  }
  *head = new_head;   // now update the head
} 

Answer 2

The task at hand will be much simpler once you undergo a slight paradigm shift. This might seem more complicated at first, but after pondering it a bit, its simplicity should be obvious.

Simply said: instead of carrying a pointer around -- to the first of each pair of list elements -- as you walk through the list, carry a pointer to the pointer to the first of each pair of list elements. This sounds complicated, on its face value; but once the dust settles, this simplifies the task at hand greatly.

You must have a head pointer stored separately, and you're passing it to swapPairs():

Node *head;

// The list gets populated here, then ...

swapPairs(head);

That's what you're doing now. But rather than doing this, pass a pointer to the head node, instead:

swapPairs(&head);

// ...

void swapPairs(Node **ptr)
{
    while ( (*ptr) && (*ptr)->next)
    {
          // swap the next two elements in the list

          // ...

          // Now, advance by two elements, after swapping them.
          ptr= &(*ptr)->next->next;
    }
}

The body of the while loop is going to swap the next two elements in the list, and let's skip over that part for now, and just focus on this bit of logic that iterates through this linked list, a pair of elements at a time. What's going on here?

Well, you are trying to walk through the list, two elements at a time.

Remember, ptr is no longer the pointer to the first element of the pair. It's a pointer to wherever the pointer to the first element of the pair happens to live. So the initial ptr is pointing to your original head pointer.

Once you understand that, the next mental leap is to understand that you want to cycle through your iteration as long as there are at least two elements left in the list:

    while ( (*ptr) && (*ptr)->next)

*ptr is the next element to the list, the first of the pair, and (*ptr)->next would therefore be the pointer to the second in the pair. Because of how we're iterating, ptr can be proven, by contract to never be NULL. So, if *ptr is NULL, you reached the end of the list. But if *ptr is not NULL, there's at least one element left, and (*ptr)->next is the "next 2nd element". If (*ptr)->next is NULL, the original list had an odd number of elements in it, so on the last iteration you ended up with *ptr pointing to the odd duck. And you're done in that case too, no need to go any further.

Finally:

ptr= &(*ptr)->next->next;

This simply advances ptr by two elements of the list. Remember, ptr is a pointer to wherever the pointer to the first of the next two elements in the list "happens to live", and this now sets ptr to point the where the pointer to the first of the ***next**** two elements in the list happens to live. Take a piece of paper, draw some diagrams, and figure this out yourself. Do not pass "Go", do not collect $200, until this sinks in.

Once you wrapped your brain around that, the only thing that's left is to swap the pairs. That's it. The body of the loop can simply be:

Node *first=*ptr;
Node *second=first->next;
Node *next=second->next;

*ptr=second;
second->next=first;
first->next=next;

That's it. You're done. And, guess what? Your original head is now automatically pointing to the right head node of the swapped list.

Now, wasn't that easy?

Answer 3

Change the signature of the function to

Node* swapPairs(Node* head)

and save the new head after the first swap, then at the end after your while loop's closing }, return that new head, to replace the old list head held by the caller, which would use this something like:

list = swapPairs(list);