LeetCode 160 Intersection Of Two Linked Lists 相交链表 Java

题目：找到两个相交列表的起始点，如图c1开始为A和B两个链表的相交点

举例1：8为两个链表的相交点。 注意：相交不止是数值上的相同。

举例2：2为相交点

举例3：没有相交点

解题思路：

相交证明最后一段链表路径完全一样，所以我利用栈先进后出的特性，把两个链表都放入栈中，然后将其相同部分放入一个新的栈中，遇到不一样的节点就结束循环。 最后从新的栈后进先出的原理，重新取到相交点的起初节点及完整路径。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        //将链表A与B分别放入栈A与B中
        Stack<ListNode> stackA = new Stack<>();
        while (headA != null) {
            stackA.push(headA);
            headA = headA.next;
        }
        Stack<ListNode> stackB = new Stack<>();
        while (headB != null) {
            stackB.push(headB);
            headB = headB.next;
        }


        //从链表的最后一个位置开始比较相同节点，相同的话放入新的栈中，不同的话结束比较
        Stack<ListNode> intersectStack = new Stack<>();
        while (!stackA.isEmpty() && !stackB.isEmpty()) {
            ListNode currectA = stackA.pop();
            ListNode currectB = stackB.pop();
            if (currectA == currectB) {
                intersectStack.push(currectA);
            } else {
                break;
            }
        }


        //将相交栈中的数据取出，重新拼成链表
        if (intersectStack.isEmpty()) {
            return null;
        }
        ListNode newHead = intersectStack.pop();
        ListNode currect = newHead;
        while (!intersectStack.isEmpty()) {
            currect.next = intersectStack.pop();
            currect = currect.next;
        }
        currect.next = null;
        return newHead;
    }
}