1

I found this code online for reversing a linked list using only 2 pointers using xor operation :

void reverse(struct Node** head_ref) 
{ 
    struct Node* prev = NULL; 
    struct Node* current = *head_ref; 

    // at last prev points to new head 
    while (current != NULL) { 
        current = (struct Node*)((ut)prev ^ (ut)current ^ (ut)(current->next) ^ (ut)(current->next = prev) ^ (ut)(prev = current)); 
    } 

    *head_ref = prev; 
}

Can you please explain how this code works ?

Harini Sj
  • 173
  • 1
  • 2
  • 11

1 Answers1

3

Have you read this: Iteratively Reverse a linked list using only 2 pointers?

   while (current != NULL) { 
        // This expression evaluates from left to right 
        // current->next = prev, changes the link fron 
        // next to prev node 
        // prev = current, moves prev to current node for 
        // next reversal of node 
        // This example of list will clear it more 1->2->3->4 
        // initially prev = 1, current = 2 
        // Final expression will be current = 1^2^3^2^1, 
        // as we know that bitwise XOR of two same 
        // numbers will always be 0 i.e; 1^1 = 2^2 = 0 
        // After the evaluation of expression current = 3 that 
        // means it has been moved by one node from its 
        // previous position 
        current = (struct Node*)((ut)prev ^ (ut)current ^ (ut)(current->next) ^ (ut)(current->next = prev) ^ (ut)(prev = current)); 
    }
David Ranieri
  • 39,972
  • 7
  • 52
  • 94
  • Yes, but I have trouble understanding that. How is prev 1 and current = 2? – Harini Sj May 16 '20 at 06:59
  • 1
    It means the previous node has 1 as value and the current one is 2, they have ascending order. This is the key: `(ut)(current->next = prev) ^ (ut)(prev = current)`, is storing addresses (`uintptr_t` is an integer type capable of holding a pointer) in a temporary using xor operations while assigning the previous node (stored in the previous iteration). Is obfuscated code and add nothing to the conventional way of doing it: https://www.geeksforgeeks.org/reverse-a-linked-list/?ref=rp – David Ranieri May 16 '20 at 07:35
  • Initially prev is NULL and current is pointing to head node which is 1. How does prev node have 1 and current node have 2 ? I still did not get it. – Harini Sj May 16 '20 at 07:54
  • 1
    The first iteration swaps the address of `NULL` (0) with the address of the first node: `0 ^ 1` (xoring any value with `0` is a NOOP), then `1 ^ 2`, then `2 ^ 3` and so on ... – David Ranieri May 16 '20 at 07:59
  • How is the address of the 1st node (current) 1? It's data is only 1 right? – Harini Sj May 16 '20 at 11:09
  • 1
    Yes, `^` is swapping addresses not values – David Ranieri May 16 '20 at 11:16
  • So, will any pointer pointing to the head node (1st node) give an address of 1 after casting the pointer with (ut) ? Is that how uintptr_t works? Sorry, for asking too many questions – Harini Sj May 16 '20 at 11:25
  • Does the swapping take place first, or does current pointer(in the LHS) move to the next node first? – Harini Sj May 16 '20 at 11:35
  • 1
    See the comment of @Molbdnilo: _That has undefined behaviour due to the unsequenced pairs prev/prev = current, and current->next/current->next = prev_ this is UB, you can not tell the order, do not use this code. – David Ranieri May 16 '20 at 11:45
  • 1
    Thank you ! Then, does that mean reversing linked list with 2 pointers is not possible (other than this code using xor) ? – Harini Sj May 16 '20 at 12:24
  • 1
    No, this code is not well defined, as I said it invokes UB, this is very well explained here: https://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points – David Ranieri May 16 '20 at 13:52