Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null
. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA == NULL || headB == NULL) return NULL; int lengthA = 1, lengthB = 1; ListNode* pa = headA; ListNode* pb = headB; while(pa->next) {lengthA++; pa = pa->next;} while(pb->next) {lengthB++; pb = pb->next;} if(pa != pb) return NULL; int diff = lengthA - lengthB; pa = headA; pb = headB; if(diff > 0){ while(diff-- > 0) pa = pa->next; }else{ while(diff++ < 0) pb = pb->next; } while(pa != pb){ pa = pa->next; pb = pb->next; } return pa; } };