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

题目描述

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

思路1：
首次遍历:算出2个链表的长度l1,l2。
第二次遍历,长的链表先走|l2-l1|步，然后2个链表同时遍历，找到第一个相同的节点输出。

 1 public class Solution {
 2     public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 3          int l1 = 0,l2 = 0,ldiff=0;
 4         ListNode longp,shortp;
 5         
 6         // 得到长度
 7         for(ListNode p = pHead1;p!=null;p=p.next)
 8             l1++;
 9         for(ListNode p = pHead2;p!=null;p=p.next)
10             l2++;
11         if(l1>l2){
12             ldiff = l1-l2;
13             longp=pHead1;shortp = pHead2;
14         }
15            else{
16              ldiff = l2-l1;
17             longp=pHead2;shortp = pHead1;
18         }
19         //长链表先走
20         for(int i = 0;i<ldiff;i++){
21             longp = longp.next;
22         }
23         //2个链表同时遍历
24         while(longp!=null){
25             if(longp.val==shortp.val) return longp;
26             longp = longp.next;
27             shortp = shortp.next;
28             
29         }
30         return null; 
31     }
32 }

C++:20180726

 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* pHead1, ListNode* pHead2) {
12         //find coross
13         ListNode* fast = pHead1;
14         ListNode* slow = pHead2;
15         int l1 = 0,l2 = 0,d=0;
16         while(fast!=NULL) {fast=fast->next;l1++;}
17         while(slow!=NULL) {slow=slow->next;l2++;}
18         if(l1>l2) {
19             fast = pHead1;
20             slow = pHead2;
21             d = l1-l2;
22         }
23         else{
24             fast = pHead2;
25             slow = pHead1;
26             d = l2-l1;
27         } 
28         
29         for(int i = 0;i<d;i++)
30             fast = fast->next;
31         while(fast!=NULL){
32             if(fast==slow)
33                     return fast;
34             fast = fast->next;
35             slow = slow->next;
36         }
37         return NULL;
38     }
39 };