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.
  找到相交的結點，很簡單的題目，用雙指針記錄兩個鏈表，如果相等則返回結點，如果沒有則一直next下去，盡頭沒有next了就返回空。當其中一個指針走完的時候，就重定向到另外一個鏈表，這樣子就可以讓兩個指針步數一致。在第二次迭代同時碰到交叉點結點。最后的時間復雜度是兩個鏈表的長度之和，考慮最壞情況O(m+n)。例:A={1,2,3,4,5},B={6,7,8,3,4,5}。A的長度比B小，A先走完了，此時B走到4的位置，A重定向后在鏈表B的6的位置，此時B走到5，然后B重定向到A鏈表的位置1，最后兩個指針距離交叉點3的步數一致。
  1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * struct ListNode *next; 6 * }; 7 */ 8 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { 9 if(!headA || !headB) return NULL; 10 struct ListNode *pa=headA,*pb=headB; 11 while(1){ 12 if(pa==pb) 13 return pa; 14 else if(!pa->next && !pb->next) 15 return NULL; 16 else{ 17 if(pa->next) 18 pa=pa->next; 19 else 20 pa=headB; 21 if(pb->next) 22 pb=pb->next; 23 else 24 pb=headA; 25 } 26 } 27 }

  ?

  看到別的大神更簡潔的寫法,同樣的原理:
  1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * struct ListNode *next; 6 * }; 7 */ 8 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { 9 if(!headA || !headB) return NULL; 10 struct ListNode *pa=headA,*pb=headB; 11 while(pa!=pb){ 12 pa=pa==NULL?headB:pa->next; 13 pb=pb==NULL?headA:pb->next; 14 } 15 return pa; 16 }

  ?

轉載于:https://www.cnblogs.com/real1587/p/9886734.html

總結

以上是生活随笔為你收集整理的160. Intersection of Two Linked Lists的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。