LeetCode 160. 相交链表
题目描述
思路分析
- 计算长度：首先计算两个链表的长度
lengthA和lengthB。- 对齐起始位置：根据长度差，先让较长的链表向前移动差值的长度，使得两个链表的剩余部分长度相同。
- 同时遍历：然后同时遍历两个链表，找到第一个相交的节点。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func getIntersectionNode(headA, headB *ListNode) *ListNode {
// 计算链表 A 的长度
lengthA := 0
for cur := headA; cur != nil; cur = cur.Next {
lengthA++
}
// 计算链表 B 的长度
lengthB := 0
for cur := headB; cur != nil; cur = cur.Next {
lengthB++
}
a, b := headA, headB
// 让较长的链表先走几步
for lengthA > lengthB {
a = a.Next
lengthA--
}
for lengthB > lengthA {
b = b.Next
lengthB--
}
// 同时遍历两个链表，找到相交节点
for a != b {
a = a.Next
b = b.Next
}
return a
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
if a != nil {
a = a.Next
} else {
a = headB
}
if b != nil {
b = b.Next
} else {
b = headA
}
}
return a
}
- 时间复杂度：
O(m + n)，其中m和n是两个链表的长度。- 空间复杂度：
O(1)，只使用了常数级别的额外空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！