首页 > 代码库 > [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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
Hide Tags
Linked List 两个单项链表,判断是否存在交集,如上图很清晰,最直观的方法是
for list1 begin to last
for list2 begin to last
if list2==list1 success
end
end
时间是O(nm),空间挺少的O(1)。如何提高呢?
- 遍历list1 ,将其节点存在hash_table
- 遍历list2,如果已经在hash_table中,那么存在
利用hash_table 可以提升时间到O(n+m),可是空间变O(n)了
1 class Solution { 2 public: 3 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 4 unordered_map<ListNode*,int> m; 5 while(headA!=NULL){ 6 m[headA] = 1; 7 headA=headA->next; 8 } 9 while(headB!=NULL){10 if(m[headB]==1) return headB;11 headB=headB->next;12 }13 return NULL;14 }15 };
那题目的最好解法,这技巧问题阿,遍历list1 后接着遍历list2,同时,遍历list2然后遍历list1,这样两个遍历的长度是一样的O(n+m),怎么判断相等呢?
list1: O O O O O ⑴ ⑵ ⑶
list2: □ □ □ □ ⑴ ⑵ ⑶
假如list 如上,⑴ ⑵ ⑶ 为相同的节点,那么遍历list1 这样便是这样:
O O O O O ⑴ ⑵ ⑶ □ □ □ □ ⑴ ⑵ ⑶
遍历list2 便是这样。
□ □ □ □ ⑴ ⑵ ⑶ O O O O O ⑴ ⑵ ⑶
合在一起看看:
O O O O O ⑴ ⑵ ⑶ □ □ □ □ ⑴ ⑵ ⑶
□ □ □ □ ⑴ ⑵ ⑶ O O O O O ⑴ ⑵ ⑶
好了,现在规律出来了。这个逻辑出来明显,主要麻烦是在遍历一个结束后接上第二个,直接改链表不好,所以,使用flag 控制。
算法逻辑:
- 判断list 是否有NULL 情况
- 同时遍历 两个新链表
- 如果节点地址相同,返回
- 如果不相同继续遍历
- 遍历结束返回NULL
1 #include <iostream> 2 #include <unordered_map> 3 using namespace std; 4 5 /** 6 * Definition for singly-linked list. 7 */ 8 struct ListNode { 9 int val;10 ListNode *next;11 ListNode(int x) : val(x), next(NULL) {}12 };13 14 /**15 class Solution {16 public:17 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {18 unordered_map<ListNode*,int> m;19 while(headA!=NULL){20 m[headA] = 1;21 headA=headA->next;22 }23 while(headB!=NULL){24 if(m[headB]==1) return headB;25 headB=headB->next;26 }27 return NULL;28 }29 };30 */31 class Solution{32 public:33 ListNode* getIntersectionNode(ListNode *headA,ListNode * headB)34 {35 ListNode * h1=headA;36 ListNode * h2=headB;37 if(headA==NULL||headB==NULL) return NULL;38 bool flag1=true,flag2=true;39 while(headA!=NULL&&headB!=NULL){40 if(headA==headB) return headA;41 headA=headA->next;42 headB=headB->next;43 if(headA==NULL&&flag1){ headA=h2; flag1 =false;}44 if(headB==NULL&&flag2){ headB=h1; flag2 =false;}45 }46 return NULL;47 }48 };49 50 int main()51 {52 ListNode head1(1);53 ListNode head2(2);54 ListNode node1(3);55 ListNode node2(4);56 head1.next = &node1;57 node1.next = &node2;58 head2.next = &node2;59 Solution sol;60 ListNode *ret = sol.getIntersectionNode(&head1,&head2);61 if(ret==NULL) cout<<"NULL"<<endl;62 else cout<<ret->val<<endl;63 return 0;64 }
[LeetCode] Intersection of Two Linked Lists 两链表是否相交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。