LeetCode 143. 重排链表
题目描述
思路分析
- 找到链表中点：使用快慢指针找到链表的中点。
- 反转后半部分链表：将链表的后半部分反转。
- 合并两个链表：将前半部分和反转后的后半部分链表合并。
参考代码
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 reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
// 使用快慢指针找到链表的中点
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
second := slow.Next
slow.Next = nil // 断开链表
// 反转后半部分链表
var pre *ListNode
cur := second
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 合并前半部分和反转后的后半部分链表
first := head
second = pre
for second != nil {
next1, next2 := first.Next, second.Next
first.Next = second
second.Next = next1
first = next1
second = next2
}
}
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
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
// 第一步：找中点
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 第二步：反转后半部分
var pre *ListNode
cur := slow.Next
slow.Next = nil // 切断前后两部分
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 第三步：合并两个链表
l1, l2 := head, pre
for l2 != nil {
next1, next2 := l1.Next, l2.Next
l1.Next = l2
l2.Next = next1
l1 = next1
l2 = next2
}
}
- 时间复杂度：O(n)，其中
n是链表的节点数。- 空间复杂度：O(1)，仅使用了常数级别的空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！