剑指Offer Java版 面试题52：两个链表的第一个公共节点

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

练习地址

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46

参考答案

/*
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;
        }
        ListNode p1 = pHead1, p2 = pHead2;
        // 得到两个链表的长度
        int len1 = 0, len2 = 0;
        while (p1 != null) {
            len1++;
            p1 = p1.next;
        }
        while (p2 != null) {
            len2++;
            p2 = p2.next;
        }
        int delta = len2 - len1;
        p1 = pHead1;
        p2 = pHead2;
        // 先在长链表上走几步，再同时在两个链表上遍历
        if (delta < 0) {
            while (delta != 0) {
                p1 = p1.next;
                delta++;
            }
        } else {
            while (delta != 0) {
                p2 = p2.next;
                delta--;
            }
        }
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 得到第一个公共节点
        return p1;
    }
}

复杂度分析

• 时间复杂度：O(m+n)。
• 空间复杂度：O(1)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题