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.
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 = 0; i < lenB - lenA; ++i) headB = headB->next; } else { for (int i = 0; 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 = 0; 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; } };
本文转自博客园Grandyang的博客，原文链接：求两个链表的交点Intersection of Two Linked Lists ，如需转载请自行联系原博主。
