LeetCode 160 Intersection Of Two Linked Lists 相交链表 Java
题目：找到两个相交列表的起始点，如图c1开始为A和B两个链表的相交点https://i-blog.csdnimg.cn/direct/3fb7cd7f4d694a9885d1b88ae403a4da.png
举例1：8为两个链表的相交点。 注意：相交不止是数值上的相同。
https://i-blog.csdnimg.cn/direct/bf0e425622e44d43aefc98713f4a463a.png
举例2：2为相交点
https://i-blog.csdnimg.cn/direct/7f2db865fe9548eb92d636d96d56a0b5.png
举例3：没有相交点
https://i-blog.csdnimg.cn/direct/48ce1c74896e424d97988ad07716dc95.png
解题思绪：
相交证明最后一段链表路径完全一样，所以我使用栈先辈后出的特性，把两个链表都放入栈中，然后将其相同部分放入一个新的栈中，遇到不一样的节点就结束循环。 最后重新的栈后进先出的原理，重新取到相交点的起初节点及完备路径。
/**
* 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;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]