题目描述

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

 

这个题本来是不准备发博客的，因为太简单了...

思路一：大致思路是先分别求出他们的长度，然后让长的先走差值步数。然后长的短的一起走，第一次相遇的节点就是结果

上代码

/*public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {         int len1=0;        int len2=0;        int len=0;        ListNode head1=pHead1;        ListNode head2=pHead2;        ListNode head11=pHead1;        ListNode head22=pHead2;        while(head1!=null){           len1++;            head1=head1.next;        }        while(head2!=null){            len2++;            head2=head2.next;        }        if((len1-len2)>0){            len=len1-len2;            for(int i=0;i

 

可是在看讨论区的时候发现了一种看起来很厉害的代码，让我陷入了沉思先po代码

class Solution {public:    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {        ListNode *p1 = pHead1;        ListNode *p2 = pHead2;        while(p1!=p2){            p1 = (p1==NULL ? pHead1 : p1->next);            p2 = (p2==NULL ? pHead2 : p2->next);        }        return p1;    }};

 

假设第一个节点长度为n，第二个节点长度为m，在有公共节点切不为null的情况下，我觉得长链表一共走了q/m遍，短链表一个走了q/n遍（q是m,n的最小公倍数）。

因为每次到null就又折回去，这样像是一个环形的链表。

还需要注意的是，当没有公共链表的时候，返回null，都是两个链表的最后一个，一个道理。  因为在循环时，短的在null的位置处理依次，长的同时后移了，所以那个长度m,n是加过null这个节点之后的，就是正常的长度+1

 

解法三

class Solution {public:    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {        ListNode *p1 = pHead1;        ListNode *p2 = pHead2;        while(p1!=p2){            p1 = (p1==NULL ? pHead2 : p1->next);            p2 = (p2==NULL ? pHead1 : p2->next);        }        return p1;    }};

这个解法和上一个解法几乎一样，只有一点点小改动，可是原理就差的多了

假设m大，n小，短的走到n的第n步跳到长的起点（新的长的），此时之前的长的走到m的第n步，两个继续走，当之前的长的走到m的第m步时跳到短的起点时，新的长的走到了(m - n)步，现在两个需要走的长度就都是n了。

只有在和大家的讨论中才能更加深入的思考。