题目描述 给你链表的头节点 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 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 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 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 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 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 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 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 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 class Solution { 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 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 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 { 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 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 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 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 暂时未解决
结果 执行用时 : ms, 击败 % 使用 Rust 的用户
内存消耗 : MB, 击败 % 使用 Rust 的用户
Racket 暂时未解决
结果 执行用时 : ms, 击败 % 使用 Racket 的用户
内存消耗 : MB, 击败 % 使用 Racket 的用户
Erlang 暂时未解决
结果 执行用时 : ms, 击败 % 使用 Erlang 的用户
内存消耗 : MB, 击败 % 使用 Erlang 的用户
Elixir 暂时未解决
结果 执行用时 : ms, 击败 % 使用 Elixir 的用户
内存消耗 : MB, 击败 % 使用 Elixir 的用户