两个链表的第一个公共结点
链表 两个 第一个 公共 结点
2023-09-14 09:07:35 时间
https://www.nowcoder.com/questionTerminal/6ab1d9a29e88450685099d45c9e31e46
描述
输入两个链表,找出它们的第一个公共结点。
解析
一般解法:
找出2个链表的长度,然后让长的先走两个链表的长度差,然后再一起走
(因为2个链表用公共的尾部)
其实没必要找2个链表长度。
用两个指针扫描”两个链表“,最终两个指针到达 null 或者到达公共结点。
比如:
假定 List1长度: a+n List2 长度:b+n, 且 a<b
那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部
接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置,还差a步就到可能的第一个公共节点。
将p2 换成 List1头部,p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。 或者p1和p2一起走n步到达列表尾部,二者没有公共节点,退出循环。 同理a>=b.
时间复杂度O(n+a+b)。
缺点:如果链表有环。。。。
代码
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (null == pHead1 || null == pHead2) { return null; } ListNode p1 = pHead1; ListNode p2 = pHead2; while (p1 != p2) { if (p1 != null) { p1 = p1.next; } if (p2 != null) { p2 = p2.next; }
if (p1 != p2) { if (p1 == null) { p1 = pHead2; } if (p2 == null) { p2 = pHead1; } } } return p1; } }
相关文章
- 找两个链表的公共节点
- 合并两个有序链表
- Java实现 LeetCode 817 链表组件(暴力)
- Java实现 LeetCode 141 环形链表
- Java实现 LeetCode 21 合并两个有序链表
- 重新整理数据结构与算法——环形链表[五]
- 合并两个有序链表
- Leetcode.1669 合并两个链表
- 合并两个有序链表
- 面试题 04.03. 特定深度节点链表-二叉树中序遍历反转
- 剑指 Offer 52. 两个链表的第一个公共节点-等长查找法
- 剑指 Offer 52. 两个链表的第一个公共节点
- leetcode 21. 合并两个有序链表 js实现
- 合并两个排序的链表
- 【日拱一卒】链表——两个有序的链表合并
- leetcode——Insertion Sort List 对链表进行插入排序(AC)
- 力扣:142. 环形链表 II
- 力扣:21. 合并两个有序链表
- 【Leetcode刷题Python】21. 合并两个有序链表
- LeetCode 92. 反转链表 II
- 【21】合并两个有序链表 【LeetCode】
- 数据结构1-1 链表