首页 > 代码库 > [LeetCode] Intersection of Two Linked Lists 两链表是否相交

[LeetCode] Intersection of Two Linked Lists 两链表是否相交

2024-08-06 16:39:21   220人阅读

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)。如何提高呢？
  1. 遍历list1 ，将其节点存在hash_table
  2. 遍历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 };
View Code

 

 
　　那题目的最好解法，这技巧问题阿，遍历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 控制。
算法逻辑：
  1. 判断list 是否有NULL 情况
  2. 同时遍历 两个新链表
  3. 如果节点地址相同，返回
  4. 如果不相同继续遍历
  5. 遍历结束返回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 }
View Code

 

 
 
 
 
 
 

[LeetCode] Intersection of Two Linked Lists 两链表是否相交


联系
我们