首页 > 代码库 > [C++]LeetCode: 60 Intersection of Two Linked Lists
[C++]LeetCode: 60 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.
Answer 1: 双指针法
思路:由于本题题意指合并,即如果两个链表有共同节点,尾部节点一定是同一个节点,即Y型。
设定两个指针,若从两个链表的表头同时遍历,很明显不能找到交点。但如果先将较长的链表截取长出去的一部分,然后两个链表同时遍历,则第一次两个指针相等的节点明显是所求节点。但若走到链表尾,仍然未相交,则两个链表未相交。
Attention:
1. 如何计算两个链表长度。
分别遍历链表,记录其长度。
while(pa) {pa=pa->next;lengthA++;} while(pb) {pb=pb->next;lengthB++;}2. 需要保存链表头结点,以备后面恢复链表指针需要。
ListNode *pa=headA,*pb=headB;复杂度:O(lengthA + lengthB) .空间复杂度O(1)
AC Code:
/** * 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) { ListNode* pa = headA; ListNode* pb = headB; //记录ListA和ListB的长度 int lengthA = 0; int lengthB = 0; while(pa) { pa = pa->next; lengthA++; } while(pb) { pb = pb->next; lengthB++; } //由于本题题意指合并,即如果两个链表有共同节点,尾部节点一定是同一个节点,即Y型,先将两个链表移动到节点个数一致的地方 if(lengthA >= lengthB) { int n = lengthA - lengthB; pa = headA; pb = headB; while(n) { pa = pa->next; n--; } } else { int n = lengthB - lengthA; pa = headA; pb = headB; while(n) { pb = pb->next; n--; } } while(pa != pb) { pa = pa->next; pb = pb->next; } return pa; } };
Answer 2: 追逐法(更加简练)
思路:根据追逐步长相同的方法,判断出如果两个链表存在交叉点,下次相遇一定在交叉点,否则在尾部节点。
算法:保存两个链表头结点,同步遍历,如果某指针达到末尾,则将其指向另外一个链表头结点。直到有相同节点或者都为NULL.
复杂度:O(lengthA + lengthB)
看下面的示意图就可以清晰明白。
AC Code:
/** * 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) { ListNode* pa = headA; ListNode* pb = headB; if(pa == NULL || pb == NULL) return NULL; while(pa != NULL && pb != NULL && pa != pb) { pa = pa->next; pb = pb->next; if(pa == pb) return pa; //追逐,下次相遇一定是在交叉点,如果没有交叉点,即终点。 if(pa == NULL) pa = headB; if(pb == NULL) pb = headA; } return pa; } };
[C++]LeetCode: 60 Intersection of Two Linked Lists
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。