剑指offer最优解Java版

剑指offer最优解Java版-两个链表的第一个公共结点

2019-07-01  本文已影响4人  全菜工程师小辉

题目描述

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

解决方法

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;
    }
}

复杂度分析:

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

猜你喜欢

热点阅读