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;}
}