Welcome everyone

每周一练(26)

每周一练 汪明鑫 661浏览 0评论

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

不要使用额外空间

 

这道题借助额外存储空间也好解

我们这里的公共节点是指引用,而不是值

 

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)return null;
        
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;

        while(p1!=p2){
            p1 = p1.next;
            p2 = p2.next;
            if(p1 != p2){
                //p1后面续上p2,p2后面续上p1   
                if(p1 == null)p1 = pHead2;
                if(p2 == null)p2 = pHead1;
            }
        }

        return p1;
    }
}

 

0-1-2-3-4-5-null
a-b-4-5-null

 

遍历后就成这样

0-1-2-3-4-5-a-b-4-5
a-b-4-5-0-1-2-3-4-5

 

这样得到2个长度一样的链表,并找到公共节点  4-5

如果找不到公共节点则返回null

 

 

 

 

if(p1 != p2) 加上这个是为了避免死循环

如果p1、p2都为null,直接return null

 

这个方法比较巧,不好想。。。

 

转载请注明:汪明鑫的个人博客 » 每周一练(26)

喜欢 (0)

说点什么

您将是第一位评论人!

提醒
avatar
wpDiscuz