描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：n<=1000

要求：空间复杂度 O(1)，时间复杂度 O(n)

思路1：统计两个链表长度

先分别统计两个链表长度，让长的先走，直到两个链表长度相等，再同时开始

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //统计两个链表长度
        int count1 = getCount(pHead1);
        int count2 = getCount(pHead2);
        int distance = count2 - count1;
        //链表长的先走，直到在同一起跑线
        if(distance > 0) {
            while(distance != 0) {
                pHead2 = pHead2.next;
                distance--;
            }
        } else if(distance < 0){
            while(distance != 0) {
                pHead1 = pHead1.next;
                distance++;
            }
        }
        //同时开始
        while(pHead1 != pHead2) {
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return pHead1;
    }
    private int getCount(ListNode node) {
        int count = 0;
        while(node != null) {
            node = node.next;
            count++;
        }
        return count;
    }
}

思路2：p1 + p2 = p2 + p1

双指针，链表1遍历完之后继续遍历链表2，链表2遍历完后继续遍历链表1，直到两个指针到达同一个节点

例如：4为公共节点，{1, 2, 4} + {3, 4} = {3, 4} + {1, 2, 4}

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1 != p2) {
            p1 = p1 != null ? p1.next : pHead2;
            p2 = p2 != null ? p2.next : pHead1;
        }
        return p1;
    }
}

思路3：集合Set

链表1遍历放入Set，链表2遍历查找Set中是否包含

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set = new HashSet<>();
        while(pHead1 != null) {
            set.add(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2 != null) {
            if(set.contains(pHead2)) {
                return pHead2;
            }
            pHead2 = pHead2.next;
        }
        return null;
    }
}