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

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

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

举例2：2为相交点

举例3：没有相交点

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

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. * int val;
5. * ListNode next;
6. * ListNode(int x) {
7. * val = x;
8. * next = null;
9. * }
10. * }
11. */
12. public class Solution {
13.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
15.         //将链表A与B分别放入栈A与B中
16.         Stack<ListNode> stackA = new Stack<>();
17.         while (headA != null) {
18.             stackA.push(headA);
19.             headA = headA.next;
20.         }
21.         Stack<ListNode> stackB = new Stack<>();
22.         while (headB != null) {
23.             stackB.push(headB);
24.             headB = headB.next;
25.         }
28.         //从链表的最后一个位置开始比较相同节点，相同的话放入新的栈中，不同的话结束比较
29.         Stack<ListNode> intersectStack = new Stack<>();
30.         while (!stackA.isEmpty() && !stackB.isEmpty()) {
31.             ListNode currectA = stackA.pop();
32.             ListNode currectB = stackB.pop();
33.             if (currectA == currectB) {
34.                 intersectStack.push(currectA);
35.             } else {
36.                 break;
37.             }
38.         }
41.         //将相交栈中的数据取出，重新拼成链表
42.         if (intersectStack.isEmpty()) {
43.             return null;
44.         }
45.         ListNode newHead = intersectStack.pop();
46.         ListNode currect = newHead;
47.         while (!intersectStack.isEmpty()) {
48.             currect.next = intersectStack.pop();
49.             currect = currect.next;
50.         }
51.         currect.next = null;
52.         return newHead;
53.     }
54. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。