题目地址
https://leetcode.com/problems/reverse-nodes-in-k-group/
题目描述
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
Note:
Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
思路
题意是以 k
个nodes为一组进行翻转,返回翻转后的linked list
.
从左往右扫描一遍linked list
,扫描过程中,以k为单位把数组分成若干段,对每一段进行翻转。给定首尾nodes,如何对链表进行翻转。
链表的翻转过程,初始化一个为null
的 previous node(prev)
,然后遍历链表的同时,当前node (curr)
的下一个(next)指向前一个node(prev)
,
在改变当前node的指向之前,用一个临时变量记录当前node的下一个node(curr.next)
. 即
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
举例如图:翻转整个链表 1->2->3->4->null
-> 4->3->2->1->null
这里是对每一组(k个nodes
)进行翻转,
-
先分组,用一个
count
变量记录当前节点的个数 -
用一个
start
变量记录当前分组的起始节点位置的前一个节点 -
用一个
end
变量记录要翻转的最后一个节点位置 -
翻转一组(
k个nodes
)即(start, end) - start and end exclusively
。 -
翻转后,
start
指向翻转后链表, 区间(start,end)
中的最后一个节点, 返回start
节点。 -
如果不需要翻转,
end
就往后移动一个(end=end.next
),每一次移动,都要count+1
.
如图所示 步骤4和5: 翻转区间链表区间(start, end)
举例如图,head=[1,2,3,4,5,6,7,8], k = 3
NOTE: 一般情况下对链表的操作,都有可能会引入一个新的
dummy node
,因为head
有可能会改变。这里head 从1->3
,
dummy (List(0))
保持不变。
复杂度分析
- 时间复杂度:
O(n) - n is number of Linked List
- 空间复杂度:
O(1)
关键点分析
- 创建一个dummy node
- 对链表以k为单位进行分组,记录每一组的起始和最后节点位置
- 对每一组进行翻转,更换起始和最后的位置
- 返回
dummy.next
.
代码 (Java/Python3
)
Java Code
class ReverseKGroupsLinkedList { public ListNode reverseKGroup(ListNode head, int k) { if (head == null || k == 1) { return head; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode start = dummy; ListNode end = head; int count = 0; while (end != null) { count++; // group if (count % k == 0) { // reverse linked list (start, end] start = reverse(start, end.next); end = start.next; } else { end = end.next; } } return dummy.next; } /** * reverse linked list from range (start, end), return last node. * for example: * 0->1->2->3->4->5->6->7->8 * | | * start end * * After call start = reverse(start, end) * * 0->3->2->1->4->5->6->7->8 * | | * start end * first * */ private ListNode reverse(ListNode start, ListNode end) { ListNode curr = start.next; ListNode prev = start; ListNode first = curr; while (curr != end){ ListNode temp = curr.next; curr.next = prev; prev = curr; curr = temp; } start.next = prev; first.next = curr; return first; } }
Python3 Cose
class Solution: def reverseKGroup(self, head: ListNode, k: int) -> ListNode: if head is None or k < 2: return head dummy = ListNode(0) dummy.next = head start = dummy end = head count = 0 while end: count += 1 if count % k == 0: start = self.reverse(start, end.next) end = start.next else: end = end.next return dummy.next def reverse(self, start, end): prev, curr = start, start.next first = curr while curr != end: temp = curr.next curr.next = prev prev = curr curr = temp start.next = prev first.next = curr return first
参考(References)
- Leetcode Discussion (yellowstone)
扩展
-
要求从后往前以
k
个为一组进行翻转。(字节跳动(ByteDance)面试题)例子,
1->2->3->4->5->6->7->8, k = 3
,从后往前以
k=3
为一组,6->7->8
为一组翻转为8->7->6
,3->4->5
为一组翻转为5->4->3
.1->2
只有2个nodes少于k=3
个,不翻转。
最后返回:
1->2->5->4->3->8->7->6
这里的思路跟从前往后以k
个为一组进行翻转类似,可以进行预处理:
-
翻转链表
-
对翻转后的链表进行从前往后以k为一组翻转。
-
翻转步骤2中得到的链表。
例子:1->2->3->4->5->6->7->8, k = 3
-
翻转链表得到:
8->7->6->5->4->3->2->1
-
以k为一组翻转:
6->7->8->3->4->5->2->1
-
翻转步骤#2链表:
1->2->5->4->3->8->7->6
类似题目
- Swap Nodes in Pairs
题目地址 https://leetcode.com/problems/optimize-water-distribution-in-a-village/ 题目描述 There are n houses in a village. We want to supply water for all the houses by building wells and …
LeetCode题解190.reverse-bits题目地址 https://leetcode.com/problems/reverse-bits/description/ 题目描述 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111…
bulit-in gradle插件的版本号是多少? - java在我的gradle构建文件中,我有以下插件块plugins { `java-library` jacoco checkstyle } 这些都没有指定版本,但是一切正常。假定一个项目正在使用gradle 6.0和gradle包装器,但是系统已安装gradle 5.0。问题:如果我运行gradle wrapper ./gradlew build,将会执行grad…
实例化类型<?>的泛型类 - java我正在为SCJP / OCPJP学习,并且遇到了一个对我来说很奇怪的示例问题。该示例代码实例化了两个通用集合:List<?> list = new ArrayList<?>(); List<? extends Object> list2 = new ArrayList<? extends Object>(); …
无法在Maven surefire中运行多个执行? - java我想运行名称以ResourceTest.java结尾的测试类,因此我在执行后定义了它们。<plugin> <groupId>org.apache.maven.plugins</groupId> <artifactId>maven-surefire-plugin</artifactId> <co…