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

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

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) {
        // 思路:求两个链表长度,让长的先走一段距离,再一起出发,遇到一样的就是第一个节点
        // 这种方法是理解起来最简单的,但是需要计算链表的长度
        // 另外一种方法,就是,把两个链表合起来看,链表1和链表2同时出发,链表1如果走完了,从链表2出发,链表2走完了,从链表1出发
        // 一样的路程,一样的速度,他们总会相遇的,第一次相遇地方就是公共节点
        
        ListNode l1 = pHead1, l2 = pHead2;
        while(l1 != l2){
            l1 = l1 == null ? pHead2 : l1.next;
            l2 = l2== null ? pHead1 : l2.next;
        }
        return l1;

 
    }
}

在思路里面我说了,最好理解方法就是,先求出长度差,然后长的先走差值长度,再比较是否相同。这种方法还需要计算链表的长度。

另外一种方法,是合并两个链表,他们的路程一样,速度一样,总会相遇的。这种情况要注意,我一开始是判断,l1.next == null ,这会出现一个问题,就是当两个链表没有重叠的时候,会陷入死循环。并且一开始还需要增加一个判断,就是一开始如果链表为空,就要输出null。

所以更改了思路,增加链表尾null,路程还是一样的,判断的是l1 == null ,如果两个链表都走到了彼此结束的地方,都为null,此时l1是等于l2的,会跳出循环,并且一开始的判断链表是否为空也不需要了。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-16 18:05
何尝不是一种学历歧视呢
下午吃泡馍:这种公司不投也罢,不过建议挂出公司名字,1.1w就应激到问是不是清北也是看得出来不是啥好公司了,估计这hr也没见过啥世面
点赞 评论 收藏
分享
Lorn的意义:你这标个前端是想找全栈吗?而且项目确实没什么含金量,技术栈太少了,边沉淀边找吧 现在学院本想就业好一点四年至少得高三模式两年加油吧
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务