题解 | #两个链表的第一个公共结点#

两个链表的第一个公共结点

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

import java.util.*;
/*
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 pointer1 = pHead1;
        ListNode pointer2 = pHead2;
        int k1 = 1;
        int k2 = 1;
        while (pointer1.next != null) {
            k1++;
            pointer1 = pointer1.next;
        }
        while (pointer2.next != null) {
            k2++;
            pointer2 = pointer2.next;
        }

        // 无交点
        if (pointer1 != pointer2) {
            return null;
        }

        // 计算两节点的差距,让长的链表先走完差距,直到两个链表一样长
        pointer1 = pHead1;
        pointer2 = pHead2;
        if (k1 > k2) {
            int distance = k1 - k2;
            for (int i = 0; i < distance; i++) {
                pointer1 = pointer1.next;
            }
        } else {
            int distance = k2 - k1;
            for (int i = 0; i < distance; i++) {
                pointer2 = pointer2.next;
            }
        }

        // 找到交叉节点
        while (pointer1 != pointer2) {
            pointer1 = pointer1.next;
            pointer2 = pointer2.next;
        }
        return pointer1;
    }
}

全部评论

相关推荐

11-05 07:29
贵州大学 Java
点赞 评论 收藏
分享
10-25 00:32
香梨想要offer:感觉考研以后好好学 后面能乱杀,目前这简历有点难
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务