52-两个链表的第一个公共节点

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

存在公共结点的链表是Y的形状。

两个链表

暴力解法

最容易想到的是暴力解法，在第一个链表上遍历节点，对每一个节点同时遍历第二个链表里的结点，如果相同说明是公共结点。

两个指针

我们假设两个链表有共同的一段链表，那么根据形状可以得知，可以用两个指针分别指向两个链表，然后让指向长链表的指针先走若干步，然后两个指针在共同的前进。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int m = calListLength(headA);//计算长度
        int n = calListLength(headB);//
        if (m > n) { 
            int gap = m - n;
            while (gap > 0) {
                headA = headA.next;
                gap--;
            }
        }else{
            int gap = n - m;
            while (gap > 0) {
                headB = headB.next;
                gap--;
            }
        }
  		//两个指针齐头并进
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }

        return null;
    }

    private int calListLength(ListNode head) {
        ListNode first = head;
        int m = 0;
        while (first != null) {
            m++;
            first = first.next;
        }
        return m;
    }

栈解法

我们可以分别遍历两个链表，将节点存储到两个栈中，然后从两个栈分别出栈，直到最后一个相同的结点就是第一个公共结点。

 public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Stack<ListNode> first = new Stack<>();
        Stack<ListNode> second = new Stack<>();
        while (headA != null) {
            first.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            second.push(headB);
            headB = headB.next;
        }
        ListNode same = null;
        while (!first.isEmpty() && !second.isEmpty()) {
            if (first.peek() == second.peek()) {
                same = first.pop();
                second.pop();
            }else{
                break;
            }
        }
        return same;
    }