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

不要使用额外空间

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

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

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）