160. Intersection of Two Linked Lists

时间：2021-12-09 16:20:44
 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 static int wing=[]()
10 {
11     std::ios::sync_with_stdio(false);
12     cin.tie(NULL);
13     return 0;
14 }();
15 class Solution 
16 {
17 public:
18     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
19     {
20         if(headA==NULL||headB==NULL)
21             return NULL;
22         ListNode *lon=headA,*sho=headB;
23         int lenA=0,lenB=0;
24         while(lon!=NULL)
25         {
26             lenA++;
27             lon=lon->next;
28         }        
29         while(sho!=NULL)
30         {
31              lenB++;
32             sho=sho->next;
33         }       
34         lon=(lenA>=lenB)? headA:headB;
35         sho=(lon==headA)?  headB:headA;
36         int diff=abs(lenA-lenB);
37         while(diff>0)
38         {
39             lon=lon->next;
40             --diff;
41         }
42         while(lon!=sho)
43         {
44             lon=lon->next;
45             sho=sho->next;
46         }
47         return lon;
48     }
49 };

下面是方法二：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 static int wing=[]()
10 {
11     std::ios::sync_with_stdio(false);
12     cin.tie(NULL);
13     return 0;
14 }();
15 class Solution 
16 {
17 public:
18     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
19     {
20         if(headA==NULL||headB==NULL)
21             return NULL;
22         ListNode *lon=headA,*sho=headB;
23         while(lon!=sho)
24         {
25             lon=lon? lon->next:headB;
26             sho=sho? sho->next:headA;
27         }
28         return lon;
29     }
30 };

第一种方法是找出两链表的长度差，把长链的指针向后移动，使得两指针以后的链长相等，再开始比较，找到公共节点。

第二种方法是把两个链表拼接一下，两个指针分别跑了一个长链和一个段链，最后必然汇聚于公共节点。

 

标签：

相关文章