力扣00025.K 个一组翻转链表


题目描述

给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

示例 1:

输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]

示例 2:

输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]

提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

进阶:你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗?


解决方法

C++

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
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev_group_end = dummy;
while (true) {
ListNode* group_start = prev_group_end->next;
ListNode* group_end = getGroupEnd(group_start, k);
if (!group_end) {
break;
}
ListNode* next_group_start = group_end->next;
group_end->next = nullptr;
prev_group_end->next = reverseList(group_start);
group_start->next = next_group_start;
prev_group_end = group_start;
}

return dummy->next;
}
private:
ListNode* getGroupEnd(ListNode* start, int k) {
for (int i = 1; i < k && start; ++i) {
start = start->next;
}
return start;
}
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* next_node = curr->next;
curr->next = prev;
prev = curr;
curr = next_node;
}
return prev;
}
};

结果

执行用时 : 14 ms, 击败 29.79% 使用 C++ 的用户

内存消耗 : 14.58 MB, 击败 7.15% 使用 C++ 的用户


Java

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
39
40
41
42
43
44
45
46
47
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy;
while (true) {
ListNode groupStart = prevGroupEnd.next;
ListNode groupEnd = getGroupEnd(groupStart, k);
if (groupEnd == null) {
break;
}
ListNode nextGroupStart = groupEnd.next;
groupEnd.next = null;
prevGroupEnd.next = reverseList(groupStart);
groupStart.next = nextGroupStart;
prevGroupEnd = groupStart;
}
return dummy.next;
}
private ListNode getGroupEnd(ListNode start, int k) {
for (int i = 1; i < k && start != null; ++i) {
start = start.next;
}
return start;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 43.32 MB, 击败 5.99% 使用 Java 的用户


Python

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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseKGroup(self, head, k):
dummy = ListNode(0)
dummy.next = head
prev_group_end = dummy
while True:
group_start = prev_group_end.next
group_end = self.get_group_end(group_start, k)
if not group_end:
break
next_group_start = group_end.next
group_end.next = None
prev_group_end.next = self.reverse_list(group_start)
group_start.next = next_group_start
prev_group_end = group_start
return dummy.next
def get_group_end(self, start, k):
for i in range(1, k):
if start:
start = start.next
return start
def reverse_list(self, head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev, curr = curr, next_node
return prev

结果

执行用时 : 32 ms, 击败 67.63% 使用 Python 的用户

内存消耗 : 13.03 MB, 击败 97.28% 使用 Python 的用户


Python3

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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
prev_group_end = dummy
while True:
group_start = prev_group_end.next
group_end = self.get_group_end(group_start, k)
if not group_end:
break
next_group_start = group_end.next
group_end.next = None
prev_group_end.next = self.reverse_list(group_start)
group_start.next = next_group_start
prev_group_end = group_start
return dummy.next
def get_group_end(self, start, k):
for i in range(1, k):
if start:
start = start.next
return start
def reverse_list(self, head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev, curr = curr, next_node
return prev

结果

执行用时 : 44 ms, 击败 87.58% 使用 Python3 的用户

内存消耗 : 17.23 MB, 击败 40.79% 使用 Python3 的用户


C

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
39
40
41
42
43
44
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* getGroupEnd(struct ListNode* start, int k);
struct ListNode* reverseList(struct ListNode* head);
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode* prev_group_end = dummy;
while (1) {
struct ListNode* group_start = prev_group_end->next;
struct ListNode* group_end = getGroupEnd(group_start, k);
if (!group_end) {
break;
}
struct ListNode* next_group_start = group_end->next;
group_end->next = NULL;
prev_group_end->next = reverseList(group_start);
group_start->next = next_group_start;
prev_group_end = group_start;
}
return dummy->next;
}
struct ListNode* getGroupEnd(struct ListNode* start, int k) {
for (int i = 1; i < k && start; ++i) {
start = start->next;
}
return start;
}
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
struct ListNode* next_node = curr->next;
curr->next = prev;
prev = curr;
curr = next_node;
}
return prev;
}

结果

执行用时 : 5 ms, 击败 60.44% 使用 C 的用户

内存消耗 : 6.59 MB, 击败 99.47% 使用 C 的用户


C#

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
39
40
41
42
43
44
45
46
47
48
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prevGroupEnd = dummy;
while (true) {
ListNode groupStart = prevGroupEnd.next;
ListNode groupEnd = GetGroupEnd(groupStart, k);
if (groupEnd == null) {
break;
}
ListNode nextGroupStart = groupEnd.next;
groupEnd.next = null;
prevGroupEnd.next = ReverseList(groupStart);
groupStart.next = nextGroupStart;
prevGroupEnd = groupStart;
}
return dummy.next;
}
private ListNode GetGroupEnd(ListNode start, int k) {
for (int i = 1; i < k && start != null; ++i) {
start = start.next;
}
return start;
}
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
}

结果

执行用时 : 81 ms, 击败 50.00% 使用 C# 的用户

内存消耗 : 43.74 MB, 击败 5.55% 使用 C# 的用户


JavaScript

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
39
40
41
42
43
44
45
46
47
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
let dummy = new ListNode(0);
dummy.next = head;
let prevGroupEnd = dummy;
while (true) {
let groupStart = prevGroupEnd.next;
let groupEnd = getGroupEnd(groupStart, k);
if (!groupEnd) {
break;
}
let nextGroupStart = groupEnd.next;
groupEnd.next = null;
prevGroupEnd.next = reverseList(groupStart);
groupStart.next = nextGroupStart;
prevGroupEnd = groupStart;
}
return dummy.next;
function getGroupEnd(start, k) {
for (let i = 1; i < k && start; ++i) {
start = start.next;
}
return start;
}
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
let nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
};

结果

执行用时 : 84 ms, 击败 34.35% 使用 JavaScript 的用户

内存消耗 : 52.97 MB, 击败 10.36% 使用 JavaScript 的用户


TypeScript

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
39
40
41
42
43
44
45
46
47
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
let dummy: ListNode = new ListNode(0);
dummy.next = head;
let prevGroupEnd: ListNode = dummy;
while (true) {
let groupStart: ListNode | null = prevGroupEnd.next;
let groupEnd: ListNode | null = getGroupEnd(groupStart, k);
if (!groupEnd) {
break;
}
let nextGroupStart: ListNode | null = groupEnd.next;
groupEnd.next = null;
prevGroupEnd.next = reverseList(groupStart);
groupStart.next = nextGroupStart;
prevGroupEnd = groupStart;
}
return dummy.next;
function getGroupEnd(start: ListNode | null, k: number): ListNode | null {
for (let i = 1; i < k && start; ++i) {
start = start.next;
}
return start;
}
function reverseList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr: ListNode | null = head;
while (curr) {
let nextNode: ListNode | null = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
}

结果

执行用时 : 79 ms, 击败 79.55% 使用 TypeScript 的用户

内存消耗 : 54.74 MB, 击败 10.46% 使用 TypeScript 的用户


PHP

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @param int $k
* @return ListNode
*/
function reverseKGroup($head, $k) {
$dummy = new ListNode(0);
$dummy->next = $head;
$prevGroupEnd = $dummy;
while (true) {
$groupStart = $prevGroupEnd->next;
$groupEnd = $this->getGroupEnd($groupStart, $k);
if (!$groupEnd) {
break;
}
$nextGroupStart = $groupEnd->next;
$groupEnd->next = null;
$prevGroupEnd->next = $this->reverseList($groupStart);
$groupStart->next = $nextGroupStart;
$prevGroupEnd = $groupStart;
}
return $dummy->next;
}
private function getGroupEnd($start, $k) {
for ($i = 1; $i < $k && $start; ++$i) {
$start = $start->next;
}
return $start;
}
private function reverseList($head) {
$prev = null;
$curr = $head;
while ($curr) {
$nextNode = $curr->next;
$curr->next = $prev;
$prev = $curr;
$curr = $nextNode;
}
return $prev;
}
}

结果

执行用时 : 13 ms, 击败 35.71% 使用 PHP 的用户

内存消耗 : 21.41 MB, 击败 7.14% 使用 PHP 的用户


Swift

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
39
40
41
42
43
44
45
46
47
48
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
let dummy = ListNode(0)
dummy.next = head
var prevGroupEnd: ListNode? = dummy
while true {
let groupStart: ListNode? = prevGroupEnd?.next
let groupEnd: ListNode? = getGroupEnd(groupStart, k)
if groupEnd == nil {
break
}
let nextGroupStart: ListNode? = groupEnd?.next
groupEnd?.next = nil
prevGroupEnd?.next = reverseList(groupStart)
groupStart?.next = nextGroupStart
prevGroupEnd = groupStart
}
return dummy.next
}
private func getGroupEnd(_ start: ListNode?, _ k: Int) -> ListNode? {
var start = start
for _ in 1..<k where start != nil {
start = start?.next
}
return start
}
private func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var curr: ListNode? = head
while curr != nil {
let nextNode: ListNode? = curr?.next
curr?.next = prev
prev = curr
curr = nextNode
}
return prev
}
}

结果

执行用时 : 36 ms, 击败 18.75% 使用 Swift 的用户

内存消耗 : 15.75 MB, 击败 6.25% 使用 Swift 的用户


Kotlin

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
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
class Solution {
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
val dummy = ListNode(0)
dummy.next = head
var prevGroupEnd: ListNode? = dummy
while (true) {
val groupStart: ListNode? = prevGroupEnd?.next
val groupEnd: ListNode? = getGroupEnd(groupStart, k)
if (groupEnd == null) {
break
}
val nextGroupStart: ListNode? = groupEnd?.next
groupEnd?.next = null
prevGroupEnd?.next = reverseList(groupStart)
groupStart?.next = nextGroupStart
prevGroupEnd = groupStart
}
return dummy.next
}
private fun getGroupEnd(start: ListNode?, k: Int): ListNode? {
var start = start
for (i in 1 until k) {
if (start == null) {
break
}
start = start.next
}
return start
}
private fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var curr: ListNode? = head
while (curr != null) {
val nextNode: ListNode? = curr?.next
curr?.next = prev
prev = curr
curr = nextNode
}
return prev
}
}

结果

执行用时 : 177 ms, 击败 87.88% 使用 Kotlin 的用户

内存消耗 : 36.66 MB, 击败 90.91% 使用 Kotlin 的用户


Dart

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
39
40
41
42
43
44
45
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode? next;
* ListNode([this.val = 0, this.next]);
* }
*/
class Solution {
ListNode? reverseKGroup(ListNode? head, int k) {
ListNode dummy = ListNode(0);
dummy.next = head;
ListNode? prevGroupEnd = dummy;
while (true) {
ListNode? groupStart = prevGroupEnd?.next;
ListNode? groupEnd = getGroupEnd(groupStart, k);
if (groupEnd == null) {
break;
}
ListNode? nextGroupStart = groupEnd.next;
groupEnd.next = null;
prevGroupEnd?.next = reverseList(groupStart);
groupStart?.next = nextGroupStart;
prevGroupEnd = groupStart;
}
return dummy.next;
}
ListNode? getGroupEnd(ListNode? start, int k) {
for (int i = 1; i < k && start != null; ++i) {
start = start.next;
}
return start;
}
ListNode? reverseList(ListNode? head) {
ListNode? prev = null;
ListNode? curr = head;
while (curr != null) {
ListNode? nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
}

结果

执行用时 : 287 ms, 击败 33.33% 使用 Dart 的用户

内存消耗 : 148.09 MB, 击败 66.67% 使用 Dart 的用户


Go

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
39
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
dummy := &ListNode{0, head}
prevGroupEnd := dummy
for {
groupStart := prevGroupEnd.Next
groupEnd := getGroupEnd(groupStart, k)
if groupEnd == nil {
break
}
nextGroupStart := groupEnd.Next
groupEnd.Next = nil
prevGroupEnd.Next = reverseList(groupStart)
groupStart.Next = nextGroupStart
prevGroupEnd = groupStart
}
return dummy.Next
}
func getGroupEnd(start *ListNode, k int) *ListNode {
for i := 1; i < k && start != nil; i++ {
start = start.Next
}
return start
}
func reverseList(head *ListNode) *ListNode {
var prev, curr *ListNode = nil, head
for curr != nil {
nextNode := curr.Next
curr.Next = prev
prev, curr = curr, nextNode
}
return prev
}

结果

执行用时 : 4 ms, 击败 72.33% 使用 Go 的用户

内存消耗 : 3.39 MB, 击败 60.50% 使用 Go 的用户


Ruby

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
39
40
41
42
43
44
45
46
# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val = 0, _next = nil)
# @val = val
# @next = _next
# end
# end
# @param {ListNode} head
# @param {Integer} k
# @return {ListNode}
def reverse_k_group(head, k)
dummy = ListNode.new(0)
dummy.next = head
prev_group_end = dummy
while true
group_start = prev_group_end.next
group_end = get_group_end(group_start, k)
break unless group_end
next_group_start = group_end.next
group_end.next = nil
prev_group_end.next = reverse_list(group_start)
group_start.next = next_group_start
prev_group_end = group_start
end
dummy.next
end
def get_group_end(start, k)
i = 1
while i < k && start
start = start.next
i += 1
end
start
end
def reverse_list(head)
prev = nil
curr = head
while curr
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
end
prev
end

结果

执行用时 : 53 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.84 MB, 击败 -% 使用 Ruby 的用户


Scala

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
/**
* Definition for singly-linked list.
* class ListNode(_x: Int = 0, next: ListNode = null) {
* var next: ListNode = next
* var x: Int = _x
* }
*/
object Solution {
def reverseKGroup(head: ListNode, k: Int): ListNode = {
var current = head
var count = 0
while (current != null && count < k) {
current = current.next
count += 1
}
if (count == k) {
var prev: ListNode = null
var nextGroupStart = current
current = head
for (_ <- 0 until k) {
val nextNode = current.next
current.next = prev
prev = current
current = nextNode
}
head.next = reverseKGroup(nextGroupStart, k)
prev
} else {
head
}
}
}

结果

执行用时 : 565 ms, 击败 20.00% 使用 Scala 的用户

内存消耗 : 57.17 MB, 击败 20.00% 使用 Scala 的用户


Rust

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Rust 的用户

内存消耗 : MB, 击败 % 使用 Rust 的用户


Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户


Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户


Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户