LeetCode 160. 相交链表
题目描述
思路分析
- 计算长度：首先计算两个链表的长度
lenA和lenB。- 对齐起始位置：根据长度差，先让较长的链表向前移动差值的长度，使得两个链表的剩余部分长度相同。
- 同时遍历：然后同时遍历两个链表，找到第一个相交的节点。
参考代码
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
33
34
35
// 计算链表长度
func getLength(head *ListNode) int {
length := 0
for head != nil {
length++
head = head.Next
}
return length
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
lenA := getLength(headA)
lenB := getLength(headB)
// 对齐两个链表的起始位置
for lenA > lenB {
headA = headA.Next
lenA--
}
for lenB > lenA {
headB = headB.Next
lenB--
}
// 同时遍历两个链表，寻找相交节点
for headA != nil && headB != nil {
if headA == headB {
return headA // 找到相交节点
}
headA = headA.Next
headB = headB.Next
}
return nil // 没有相交节点
}
- 时间复杂度：
O(m + n)，其中m和n是两个链表的长度。- 空间复杂度：
O(1)，只使用了常数级别的额外空间。
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
许可协议，转载请注明出处！