使用双指针 找出两个链表的第一个公共节点

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

http://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46

分析:
公共节点之后的节点都是相同的,或者说公共节点之后的部分都是相同的,所以要返回第一个公共节点,让两个链表同时走,短的走完走长的,长的走完走短的,那么一定可以遇到公共节点:
情况1、长度相同:
1.1有公共节点,那么公共节点后面是相同的,所以节点位置一定相同,两个链表齐头并进一定可以找到;
1.2无公共节点,那么一起走到最后都是null,也可以返回null
情况2、长度不同:
2.1有公共节点,那么单程短的先走完接着走长的,长的走完接着走短的,长+短 = 短+长,两路最后还是一样的,从后往前看公共节点后面部分相同,一定能碰到公共节点;
2.2无公共节点,那么长+短 和 短+长两路最后没有公共部分,但是最终长度相等,共同走到null

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2){
            p1 = (p1 == null ? pHead2 : p1.next);
            p2 = (p2 == null ? pHead1 : p2.next);
        }
        return p1;
    }
}
全部评论

相关推荐

自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 10:56
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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