由一道很简单的求两条链表的第一个公共节点的问题引发的思考

题目描述

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

 

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

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

上代码

/*
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<len;i++){
                head11=head11.next;
            }
        }else{
            len=len2-len1;
            for(int i=0;i<len;i++){
                head22=head22.next;
            }
        }
        while(head11!=null){
            if(head11==head22){
                return head11;
            }
            head11=head11.next;
            head22=head22.next;
        }
        return null;
        
    }
}

可是在看讨论区的时候发现了一种看起来很厉害的代码，让我陷入了沉思先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了。

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