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

解法1：双指针法

创建两个指针p1和p2,分别指向两个链表的头结点，然后依次往后遍历。如果某个指针到达末尾，则将该指针指向另一个链表的头结点；如果两个指针所指的节点相同，则循环结束，返回当前指针指向的节点。比如两个链表分别为：1->3->4->5->6和2->7->8->9->5->6。短链表的指针p1会先到达尾部，然后重新指向长链表头部，当长链表的指针p2到达尾部时，重新指向短链表头部，此时p1在长链表中已经多走了k步(k为两个链表的长度差值)，p1和p2位于同一起跑线，往后遍历找到相同节点即可。其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤。

时间复杂度：O(m+n), m，n分别为链表A，B的长度，
最坏情况下，公共结点为最后一个，需要遍历m+n个结点
空间复杂度：O(1)

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==null ? pHead2 : p1.next;
            p2 = p2==null ? pHead1 : p2.next;
        }
        return p1;
    }

解法2：哈希

使用HashSet，解决有环无环，相交不相交的情况

import java.util.HashSet;
/*
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;
        }
        HashSet<ListNode> set1=new HashSet<>();
        HashSet<ListNode> set2=new HashSet<>();
        while(pHead1!=null && !set1.contains(pHead1)){
            set1.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null && !set2.contains(pHead2)){
            set2.add(pHead2);
            if(set1.contains(pHead2)){
                return pHead2;
            }
            pHead2=pHead2.next;
        }
        return null;
    }
}

解法3：栈

我们发现，公共部分一定是在尾部，如果我们从后面开始找会更快，最后一个相同点就是我们要找的点，不过这是单向链表，所以我们想到了栈的结构——后进先出

解法4：求差法

其实我们用栈，只是为了想同时能到达两个链表的尾节点。当两链表长度不同时，我们从头开始遍历，到后面的时间就不一致。我们可以先遍历两个链表，得到它们的长度，然后，链表长的先走先走多的几个节点，接着同时在两个链表遍历，找到的第一个相同点就是我们要找的第一个公共点

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null) return null;
        // 求两链表的长度
        int count1 = 0;
        ListNode p1 = pHead1;
        while(p1 != null) {
            p1 = p1.next;
            count1++;
        }
        int count2 = 0;
        ListNode p2 = pHead2;
        while(p2 != null) {
            p2 = p2.next;
            count2++;
        }
        // 将长链表的指针移动到和短链表相同长度的位置
        int flag = count1-count2;
        if(flag > 0) {
            while(flag > 0) {
                pHead1 = pHead1.next;
                flag--;
            }
            while(pHead1 != pHead2) {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead1;
        }
        else {
            flag = -flag;
            while(flag > 0) {
                pHead2 = pHead2.next;
                flag--;
            }
            while(pHead1 != pHead2) {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead2;
        }
    }
}

有环思路：较为麻烦

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            if (pHead1 == null || pHead2 == null) {
                return null;
            }
            ListNode loop1 = getLoopNode(pHead1);
            ListNode loop2 = getLoopNode(pHead2);
            if (loop1 == null && loop2 == null) {
                return noLoop(pHead1, pHead2);
            }
            if (loop1 != null && loop2 != null) {
                return bothLoop(pHead1, loop1, pHead2, loop2);
            }
            return null;
        }

        private ListNode getLoopNode(ListNode pHead) {
            if (pHead == null || pHead.next == null || pHead.next.next == null) {
                return null;
            }
            ListNode n1 = pHead.next;
            ListNode n2 = pHead.next.next;
            while (n1 != n2) {
                if (n2.next == null || n2.next.next == null) {
                    return null;
                }
                n1 = n1.next;
                n2 = n2.next.next;
            }
            n2 = pHead;
            while (n1 != n2) {
                n1 = n1.next;
                n2 = n2.next;
            }
            return n1;
        }

        private ListNode noLoop(ListNode pHead1, ListNode pHead2) {
            ListNode cur1 = pHead1;
            ListNode cur2 = pHead2;
            int n = 0;
            while (cur1.next != null) {
                cur1 = cur1.next;
                n++;
            }
            while (cur2.next != null) {
                cur2 = cur2.next;
                n--;
            }
            if (cur1 != cur2) {
                return null;
            }
            cur1 = n > 0 ? pHead1 : pHead2;
            cur2 = cur1 == pHead1 ? pHead2 : pHead1;
            n = Math.abs(n);
            while (n != 0) {
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }

        private ListNode bothLoop(ListNode pHead1, ListNode loop1, ListNode pHead2, ListNode loop2) {
            ListNode cur1 = null;
            ListNode cur2 = null;
            if (loop1 == loop2) { //先相交，在共享同一个环
                cur1 = pHead1;
                cur2 = pHead2;
                int n = 0;
                while (cur1 != loop1) {
                    cur1 = cur1.next;
                    n++;
                }
                while (cur2 != loop2) {
                    cur2 = cur2.next;
                    n--;
                }
                cur1 = n > 0 ? pHead1 : pHead2;
                cur2 = cur1 == pHead1 ? pHead2 : pHead1;
                n = Math.abs(n);
                while (n != 0) {
                    cur1 = cur1.next;
                    n--;
                }
                while (cur1 != cur2) {
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                }
                return cur1;
            } else {
                cur1 = loop1.next;
                while (cur1 != loop1) {
                    if (cur1 == loop2) { //在环的某处相遇
                        return loop1;
                    }
                    cur1 = cur1.next;
                }
                return null; //各自成环
            }
        }