首页 > 代码库 > [LintCode] Intersection of Two Linked Lists 求两个链表的交点
[LintCode] Intersection of Two Linked Lists 求两个链表的交点
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 → b3begin 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; }};
[LintCode] Intersection of Two Linked Lists 求两个链表的交点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。