Reversing a linked list iteratively using only 2 pointers

Given a linked list, write the non-recursive function to reverse the list. If Input list is

1 -> 2 -> 3 -> 4 -> 5

Then, output should be

5 -> 4 -> 3 -> 2 -> 1

We have seen the recursive and non-recursive functions to reverse the list.

In the non-recursive version, we take three pointers pointing to original list, reversed list and current node.

Solution

In this solution, we use the logic given in this post to swap two variables without using third variable.

I suggest you to please go thru this post also before reading further. We use similar logic here, we keep two pointers and manipulate the three (prev, current and next pointers) thru these two pointers using XOR.

Node *reverse(Node *h)
{
  // SINGLE NODE LIST IS ALREADY REVERSED
  if (h == NULL || h->next == NULL)
    return h;
  // x POINTS TO THE REVERSED LIST
  Node *x = NULL;
  while (h != 0) {
    x = (Node*)((uintptr_t)x ^ (uintptr_t)h->next);
    h->next = (Node*)((uintptr_t)x ^ (uintptr_t)h->next); // h->next now has prev.
    x = (Node*)((uintptr_t)x ^ (uintptr_t)h->next);       // x now has h->next
    // AT THIS POINT h POINTS TO HEAD OF REVERSE LIST
    // AND x POINTS TO HEAD OF (REMAINING) ORIGINAL LIST.
    // WE JUST NEED TO SWAP THE TWO VARIABLES (x AND h) NOW.
    x = (Node*)((uintptr_t)x ^ (uintptr_t)h);
    h = (Node*)((uintptr_t)x ^ (uintptr_t)h);
    x = (Node*)((uintptr_t)x ^ (uintptr_t)h);
  }
  return x;
}

It appear to be an interesting method, but it may not have any practical advantage (memory or time) as compared to the non-recursive function that use three pointers. A simple note, is that bitwise operators are more efficient than corresponding arithmetic or relational operators.