使用 XOR 运算仅使用 2 个指针反转链表

Question

我在网上找到了这段代码，用于使用异或运算仅使用 2 个指针来反转链表：

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; 
}

你能解释一下这段代码是如何工作的吗？

Answer 1

你读过这个吗：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)); 
    }

使用 XOR 运算仅使用 2 个指针反转链表

Reverse a linked list using only 2 pointers using XOR operation

c++

pointers

linked-list

xor