您现在的位置是:首页 >其他 >LeetCode:25. K 个一组翻转链表网站首页其他
LeetCode:25. K 个一组翻转链表
简介LeetCode:25. K 个一组翻转链表
1)题目
给你链表的头节点 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) 额外内存空间的算法解决此问题吗?
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2)思路
例子:head = [1,2,3,4], k = 3
(length -= k) >= 0 true (length -= k) >= 0 false retuen 3 -> 2 -> 1 -> 4;
初始
1 -> 2 -> 3 -> 4
head s e
w
第一轮翻转之后
2 -> 1 -> 3 -> 4
head e s
w
listNode = start;
2 -> 1 -> 3 -> 4
head s e
w
第二轮翻转
3 -> 2 -> 1 -> 4
head e s
w
listNode = start;
3 -> 2 -> 1 -> 4
head s e
w
3)代码
public static ListNode reverseKGroup(ListNode head, int k) {
if (k == 1) return head;
ListNode headNode = new ListNode();
headNode.next = head;
ListNode listNode = headNode;
// 计算链表长度
int length = 0;
while (head != null) {
head = head.next;
++length;
}
while ((length -= k) >= 0) {
ListNode start = listNode.next;
for (int i = 0; i < k - 1; i++) { // k个进行翻转,翻转k-1次
ListNode wait = listNode.next; // 该节点始终指向头结点的后一位
ListNode end = start.next;
listNode.next = end;
start.next = end.next;
end.next = wait;
}
listNode = start;
}
return headNode.next;
}
4)结果
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。