剑指offer-两个链表的第一个公共结点

题目描述

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

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
           

思路

有公共结点的链表的特点：两个链表从某一结点开始，他们的next指向同一个结点。

当两个链表长度不同时，如果从头遍历到尾结点时间不一致。

所以首先第一次遍历两个链表得到各自的长度，可知哪个链表长，以及长多少（比如为lenDif）。

第二次遍历，在较长的链表先走lenDif，然后同时遍历两个链表，找到的第一个相同的结点就是第一个公共结点。

java实现

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1==null ||pHead2==null)
            return null;
        //计算两个链表的长度
        int len1=GetListLength(pHead1);
        int len2=GetListLength(pHead2);
        int lenDif=0;
        ListNode pLong=null;
        ListNode pShort=null;
        //设置长短链表的头指针，以及长度差lenDif
        if(len1>len2){
            lenDif=len1-len2;
            pLong=pHead1;
            pShort=pHead2;
        }
        else{
            lenDif=len2-len1;
            pLong=pHead2;
            pShort=pHead1;
        }
        //长链表先走lenDif步，使得剩下的长度一样
        for(int i=0;i<lenDif;i++){
            pLong=pLong.next;
        }
        //此时剩下的长度一样，同时遍历
        while (pLong!=null && pShort!=null && pLong!=pShort){
            pLong=pLong.next;
            pShort=pShort.next;
        }
        return pLong;
    }

    int GetListLength(ListNode pHead){
        int length=0;
        while (pHead.next!=null){
            length++;
            pHead=pHead.next;
        }
        return length;
    }
}