LeetCode Intersection of Two Linked Lists

LeetCode Intersection of Two Linked Lists

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.

```class Solution {
public:
int len1 = 0, len2 = 0;
ListNode *h1 = headA, *h2 = headB;
while(h1){
++len1;
h1 = h1->next;
}
while(h2){
++len2;
h2 = h2->next;
}
if(len1 > len2){
while(len1 > len2){
h1 = h1->next;
--len1;
}
} else if(len2 > len1) {
while(len2 > len1){
h2 = h2->next;
--len2;
}
}
while(h1 && h2 && h1 != h2){
h1 = h1->next;
h2 = h2->next;
}
if(!h1 || !h2)return NULL;
else return h1;
}
};
```

```class Solution {
public:
if(headA == NULL || headB == NULL) return NULL;
ListNode *h1 = headA, *h2 = headB;
ListNode *tail1 = NULL, *tail2 = NULL;
while(true){
if(h1 == NULL) h1 = headB;
if(h2 == NULL) h2 = headA;

if(h1->next == NULL) tail1 = h1;
if(h2->next == NULL) tail2 = h2;

if(tail1 != NULL && tail2 != NULL && tail1 != tail2) return NULL;

if(h1 == h2) return h1;

h1 = h1->next;
h2 = h2->next;
}
}
};
```