DEV Community

Alexander Crescent

Posted on

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

DEV Community

An Animated Guide to Node.js Event Loop

Node.js doesn’t stop from running other operations because of Libuv, a C++ library responsible for the event loop and asynchronously handling tasks such as network requests, DNS resolution, file system operations, data encryption, etc.

What happens under the hood when Node.js works on tasks such as database queries? We will explore it by following this piece of code step by step.