LeetCode 25. K 个一组翻转链表
题目描述
思路分析
- 检查链表长度：首先需要检查链表的长度，如果长度小于
k，则不需要翻转，直接返回原链表。- 翻转链表：使用双指针的方法，翻转每
k个节点。可以使用一个pre指针来指向翻转后的部分的尾部。- 连接翻转后的部分：在翻转完成后，需要将翻转后的部分与未翻转的部分连接起来。
参考代码
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 reverseKGroup(head *ListNode, k int) *ListNode {
// 计算链表的长度
length := 0
cur := head
for cur != nil {
length++
cur = cur.Next
}
dummy := &ListNode{Next: head}
preGroupEnd := dummy
for length >= k {
// 翻转 k 个节点
cur = preGroupEnd.Next
nextGroupStart := cur
var pre *ListNode
for i := 0; i < k; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
// 连接翻转后的部分
preGroupEnd.Next = pre
nextGroupStart.Next = cur
// 更新 preGroupEnd 和剩余长度
preGroupEnd = nextGroupStart
length -= k
}
return dummy.Next
}
- 时间复杂度：O (n)，其中 n 是链表的长度。每个节点都被访问一次。
- 空间复杂度：O (1)，只使用了常数级别的额外空间。
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
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k == 1 {
return head
}
tail := head
for i := 0; i < k; i++ {
if tail == nil {
return head
}
tail = tail.Next
}
newHead := reverse(head, tail)
head.Next = reverseKGroup(tail, k)
return newHead
}
func reverse(head *ListNode, tail *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != tail {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！