使用XOR操作反转只有2个指针的链接列表。

Question

我在网上找到了这段代码，用于反转一个只使用2个指针的链接列表，使用xor操作。

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

你读过这个吗？只用2个指针反复反转一个链接的列表?

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