找两个链表的公共节点
2023-09-14 08:57:28 时间
首先考虑两个链表无环的情况。
将链表a的尾节点指向头节点从而形成环。用快慢指针遍历链表b,一个一次移动2单位,另一个移动1单位。如果不相遇则不存在公共节点。如果相遇,则让其中一个指针指向b,两个指针以1单位/次的速度移动,直到相遇。相遇时指向的节点就是公共节点的起始。最后记得将a的尾节点恢复。代码如下。
其次考虑有环的情况。用快慢指针探测a中是否有环。如果有则,将使p指向a的尾节点,p的next指向null。按照上面的方法遍历b。如果遍历的过程中遇到p,则将p指向a继续遍历。如果未遇到p或者无环,则不存在公共节点。最后仍然将a的尾节点恢复。
static class LinkedList { LinkedList next; public LinkedList(LinkedList next) { this.next = next; static LinkedList calc(LinkedList a, LinkedList b) { // set tail point to a LinkedList p = a; while (p.next != null) { p = p.next; p.next = a; if (b == null || b.next == null) return null; LinkedList fast = b.next.next, slow = b.next; while (fast != null fast.next != null fast != slow) { fast = fast.next.next; slow = slow.next; if (fast != slow) { return p.next = null; } else { slow = b; while (fast != slow) { fast = fast.next; slow = slow.next; p.next = null; return slow; public static void main(String[] args) { LinkedList common = new LinkedList(new LinkedList(new LinkedList(null))); LinkedList a = new LinkedList(new LinkedList(common)); LinkedList b = new LinkedList(new LinkedList(new LinkedList( new LinkedList(common)))); LinkedList r = calc(a, b); System.out.println(r == common); }
相关文章
- 循环链表的基本操作
- 删除链表倒数第n个节点
- STL--双端队列(deque)和链表(list)
- Java实现 LeetCode 160 相交链表
- Java实现 LeetCode 24 两两交换链表中的节点
- Java实现 LeetCode 19删除链表的倒数第N个节点
- Java实现 蓝桥杯VIP 算法训练 链表数据求和操作
- 反转链表
- 【LeetCode 19】删除链表的倒数第N个节点
- Algorithm:C++语言实现之链表相关算法(链表相加、链表的部分翻转、链表划分、链表去重、重复元素全部删除)
- 【华为OD机试Python实现】HJ48 从单向链表中删除指定值的节点(中等)
- 2130. 链表最大孪生和-辅助数组存储法
- 剑指 Offer 18. 删除链表的节点
- 从jvm的角度考虑链表是如和存储的,并手写Java单向链表的,问题难在节点和头节点的对象引用
- [LeetCode] 382. 链表随机节点 ☆☆☆(随机算法:蓄水池抽样)
- 删除链表中的反复节点
- 力扣:24. 两两交换链表中的节点
- 【Leetcode刷题Python】328. 奇偶链表
- 剑指 Offer 52. 两个链表的第一个公共节点
- 剑指 Offer 22. 链表中倒数第k个节点
- LeetCode 430. 扁平化多级双向链表