Write a program to find the node at which the intersection of two singly linked lists begins.
Notice
- 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.
Have you met this question in a real interview?
Example
The following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Challenge
Your code should preferably run in O(n) time and use only O(1) memory.
LeetCode上的原题，请参见我之前的博客Intersection of Two Linked Lists。
解法一：
class Solution {
public:
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
int lenA = getLength(headA), lenB = getLength(headB);
if (lenA < lenB) {
for (int i = ; i < lenB - lenA; ++i) headB = headB->next;
} else {
for (int i = ; i < lenA - lenB; ++i) headA = headA->next;
}
while (headA && headB && headA->val != headB->val) {
headA = headA->next;
headB = headB->next;
}
return (headA && headB) ? headA : NULL;
}
int getLength(ListNode* head) {
int cnt = ;
while (head) {
++cnt;
head = head->next;
}
return cnt;
}
};
解法二：
class Solution {
public:
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
ListNode *a = headA, *b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};