剑指offer—两个链表公共节点 解答

剑指offer—两个链表公共节点

题目描述

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

思路

两个链表同一个节点以及后面的节点都是相同的,所以有一段相同的序列,从相同节点开始。

如果两个链表长度相等,我们可以每次把两个链表都往后移动一位,直到遇到相同的节点;但是如果链表长度不相等,我们需要先让长的链表的指针先遍历到与短链表距离相同节点长度相等的节点处。(图第二个链表需要先走到9节点处,然后两个链表在一同移动)

流程:

  1. 计算两个链表长度
  2. 长链表移动到长度相同位置
  3. 两个链表迭代移动,直到遇到相同节点

代码

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;ListNode p2 = pHead2;
        int l1 = 0;int l2 = 0;
        while(pHead1!=null){
            pHead1 = pHead1.next;
            l1++;
        }
        while(pHead2!=null){
            pHead2 = pHead2.next;
            l2++;
        }
        int l = l2-l1;
        for(int i=0;i<Math.abs(l);i++){
            p1 = l>0?p1:p1.next;
            p2 = l<0?p2:p2.next;
        }
        while(p1!=p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}