LeetCode-Reverse Nodes in K-Group

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

因为题目要求空间复杂度为常数,并且不能改变链表节点中元素的值,所以只能从移动链表上去想。

最开始的想法是按照最直接的思路,先判断是否可以逆转,如果可以的话就使用一个双层循环去逆转(每一轮将前面的一个元素移动到最后),这样的复杂度是 O(n^3),居然 Accept 了。但是的确效率太低了。

ps:在移动链表的时候一定要想清楚上一步对其产生的影响,不然肯定全都是 bug 呀。

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
36
37
38
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
if head==nil {
return nil
}
ret:=new(ListNode)
ret.Next=head
start,nextRound:=ret,ret
Loop:
for {
for i:=0;i<k;i++ {
if nextRound.Next==nil {
break Loop
}
nextRound=nextRound.Next
}
nextRound=start.Next
for i:=k-1;i>0;i-- {
now:=start
for j:=0;j<i;j++ {
t:=now.Next
now.Next=t.Next
t.Next=now.Next.Next
now.Next.Next=t
now=now.Next
}
}
start=nextRound
}

return ret.Next
}

看了一下 Discussion 中的思路,使用了递归和分段逆转,递归利用了我的解法中判断是否符合循环,使其不至于被浪费。而逆转算法比我高效很多,我的方法是挨个遍历,他的算法是直接将每一步的箭头倒转过来。

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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
n:=head
i:=0
for n!=nil && i<k {
n=n.Next
i++
}
if i==k {
n=reverseKGroup(n,k)
for ;i>0;i-- {
t:=head.Next
head.Next=n
n=head
head=t
}
head=n
}
return head
}

发现效率提高了一些,但是还是远远没有达到排名前面答案的水准。

于是打开排名靠前的答案看了一下,发现它们都没有遵循题目中的限制条件,所以就暂且不管了。