37 两个链表的第一个公共结点

时间：2022-10-04 11:06:55

输入两个链表，找出它们的第一个公共结点。

 

C++:

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindFirstCommonNode( ListNode* headA, ListNode* headB) {
12         ListNode* p1 = headA ;
13         ListNode* p2 = headB ;
14         if (p1 == NULL || p2 == NULL)
15             return NULL ;
16         while(p1 != p2){
17             if (p1 == NULL)
18                 p1 = headB ;
19             else
20                 p1 = p1->next ;
21             if (p2 == NULL)
22                 p2 = headA ;
23             else
24                 p2 = p2->next ;
25         }
26         return p1 ;
27     }
28 };

 

 

遍历得到两个链表的长度，求出他们之差，用的长的链表先走若干步，接着在同时在两个链表 上遍历，找到的第一个相同的结点就是他们的共同的结点

 

C++:

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     int GetListLen(ListNode* pHead){
12         int len = 0 ;
13         ListNode * pNode = pHead ;
14         while(pNode != NULL){
15             len++ ;
16             pNode = pNode->next ;
17         }
18         return len ;
19     }
20     
21     ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
22         int len1 = GetListLen(pHead1) ;
23         int len2 = GetListLen(pHead2) ;
24         int lenDif = len1 - len2 ;
25         ListNode * pHeadLong = pHead1 ;
26         ListNode * pHeadShort = pHead2 ;
27         if (len2 > len1){
28             lenDif = len2 - len1 ;
29             pHeadLong = pHead2 ;
30             pHeadShort = pHead1 ;
31         }
32         for (int i = 0 ; i < lenDif ; i++){
33             pHeadLong = pHeadLong->next ;
34         }
35         while(pHeadLong != pHeadShort && pHeadLong != NULL && pHeadShort != NULL){
36             pHeadLong = pHeadLong->next ;
37             pHeadShort = pHeadShort->next ;
38         }
39         return pHeadLong ;
40     }
41 };

 

标签：

相关文章