php实现找两个链表的第一个公共结点（实例演示）

一、总结

因为是链表，第一个节点公共之后，后面所有的节点都公共了

画个图实例演示一下，会超清晰且简单

二、php实现找两个链表的第一个公共结点

题目描述

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

三、代码

代码一：

 1 /*
 2 找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走
 3 （因为2个链表用公共的尾部）
 4 */
 5 class Solution {
 6 public:
 7     ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
 8         int len1 = findListLenth(pHead1);
 9         int len2 = findListLenth(pHead2);
10         if(len1 > len2){
11             pHead1 = walkStep(pHead1,len1 - len2);
12         }else{
13             pHead2 = walkStep(pHead2,len2 - len1);
14         }
15         while(pHead1 != NULL){
16             if(pHead1 == pHead2) return pHead1;
17             pHead1 = pHead1->next;
18             pHead2 = pHead2->next;
19         }
20         return NULL;
21     }
22      
23     int findListLenth(ListNode *pHead1){
24         if(pHead1 == NULL) return 0;
25         int sum = 1;
26         while(pHead1 = pHead1->next) sum++;
27         return sum;
28     }
29      
30     ListNode* walkStep(ListNode *pHead1, int step){
31         while(step--){
32             pHead1 = pHead1->next;
33         }
34         return pHead1;
35     }
36 };

1->2->3->4->5->6->7->8

9->4->5->6->7->8

代码二：

用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点。

不用记长度

两个链表一定有交点的话，方法是指向短链表指针先走完，然后指向长链表，指向长链表指针后走完，指向短链表。所以，第二次走过，一定会在交点相遇

如果两个链表的长度相同并且没有相同的结点，这是死循环

 1 class Solution {
 2 public:
 3     ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
 4         ListNode *p1 = pHead1;
 5         ListNode *p2 = pHead2;
 6         while(p1!=p2){
 7             p1 = (p1==NULL ? pHead2 : p1->next);
 8             p2 = (p2==NULL ? pHead1 : p2->next);
 9         }
10         return p1;
11     }
12 };

1->2->3->4->5->6->7->8 9->4->5->6->7->8

9->4->5->6->7->8 1->2->3->4->5->6->7->8