[LeetCode题解]160. 相交链表 | 双指针 + 哈希表
2024-10-10 09:08:54
方法一：双指针
解题思路
假设链表存在相交时，headA 的长度为 a + c，headB 的长度为 b + c。如果把 headA 连上 headB，headB 连上 headB 的话，当遍历这两个新链表时有：
\[(a + c) + (b + c) = (b + c) + (a + c)
\]
\]
而 \(a + c + b = b + c + a\)，就出现相交的位置，因为 c 是相交部分的长度。
假设链表不相交，那么最后也会“相交”，“相交”于链表的尾部，即 null。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
ListNode pa = headA, pb = headB;
while(pa != pb) {
pa = pa == null ? headB : pa.next;
pb = pb == null ? headA : pb.next;
}
return pa;
}
}
复杂度分析
- 时间复杂度：\(O(m+n)\)，其中 \(m\) 是
headA的长度， \(n\) 是headB的长度。 - 空间复杂度：\(O(1)\)。
方法二：哈希表
解题思路
两次遍历，第一次遍历把 headA 的节点放到哈希表里，然后第二次遍历 headB ，判断节点是否在哈希表里，如果在，就是相交的起始点。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> hash = new HashSet<ListNode>();
ListNode cur = headA;
while(cur != null) {
hash.Add(cur);
cur = cur.next;
}
cur = headB;
while(cur != null) {
if(hash.Contains(cur)) {
break;
}
cur = cur.next;
}
return cur;
}
}
复杂度分析
- 时间复杂度：\(O(m+n)\)，其中 \(m\) 是
headA的长度， \(n\) 是headB的长度。 - 空间复杂度：\(O(m)\)，其中 \(m\) 是
headA的长度。
最新文章
- 新建structs2 web应用及structs.xml常用基础配置
- js或css文件后面的参数是什么意思？
- netstat
- ASP.NET MVC 多语言实现——URL路由
- 关于对CSS尺寸单位'em'的长期误解
- maven总结1
- 利用JSONP进行水坑攻击
- Linux学习之nfs实例
- Jenkins简明入门(三) -- Blue Ocean，让一切变得简单
- Jenkins+Git+Gitlab+Ansible实现持续集成自动化部署动态网站（二）--技术流ken
- Improved GAN
- Java GC机制
- Html5 标签三（图片）
- A1051. Pop Sequence
- 涉及不同实例不同数据库的同一条sql语句
- javascript节点操作appendChild()
- ROS+nfdump 用户上网日志
- （zxing.net）一维码EAN 13的简介、实现与解码
- Python 位运算符 逻辑运算符 成员运算符
- 一些参考网站 - Reference Documentation - Website Address