剑指offer最优解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 length1 = getLength(pHead1);
        int length2 = getLength(pHead2);
        // 两链表的长度差
        // 如果链表1的长度大于链表2的长度
        if (length1 >= length2) {
            int len = length1 - length2;
            // 先遍历链表1，遍历的长度就是两链表的长度差
            while (len > 0) {
                pHead1 = pHead1.next;
                len--;
            }
        }
        // 如果链表2的长度大于链表1的长度
        else if (length1 < length2) {
            int len = length2 - length1;
            // 先遍历链表1，遍历的长度就是两链表的长度差
            while (len > 0) {
                pHead2 = pHead2.next;
                len--;
            }
        }
        // 开始齐头并进，直到找到第一个公共结点
        while(pHead1!=pHead2){
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
        return pHead1;
    }
    // 求指定链表的长度
    public static int getLength(ListNode pHead) {
        int length = 0;
        while (pHead != null) {
            length++;
            pHead = pHead.next;
        }
        return length;
    }
}

复杂度分析：

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

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我