Leetcode intersection of two linked lists

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49899/C++-solution-using-XOR-trick

Start from this:

   (p) a1 → a2
               ↘
                 X → c1 → c2
               ↗            

(q) b1 → b2 → b3

follow p, reversing links as you go:

      a1 ← a2
              ↖
                X ← c1 ← c2 (p)
              ↗            

(q) b1 → b2 → b3

now reverse q:

  (q) a1 → a2
              ↘
                X ← c1 ← c2 (p)
              ↙            
 b1 ← b2 ← b3

then reverse p again:

  (q) a1 → a2
              ↘
                X → c1 → c2
              ↗            

(p) b1 → b2 → b3

Notice that p and q are swapped, but the list structure is back to what it was in the beginning.

Now the key observation: each node in branches a, b and c has been visited exactly twice, while X has been visited three times. We can thus use the well known trick: we keep an accumulator and XOR it to each address we visit along the way. In the end, the accumulator will contain the address of the only node visited an odd number of times, that is X.

What if the lists don't meet? In that case we have already reversed p twice, reverting it to its initial state, so we only need to reverse q a second time as well and return null.

Code

class Solution {
uintptr_t acc = 0;

ListNode* reverse(ListNode *head) {
    ListNode *prev = nullptr, *tmp;
    while (head) {
        acc ^= reinterpret_cast<uintptr_t> (head);
        tmp = head->next;
        head->next = prev;
        prev = head;
        head = tmp;
    }
    return prev;
}

public:
ListNode getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p = headA, *q = headB;
p = reverse(p);
q = reverse(q);
p = reverse(p);
if (q != headA) q = reverse(q);
return reinterpret_cast<ListNode> (acc);
}
};