|
开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 29 天，点击查看活动详情
25. 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 next = newHead;
// 移动指针（正在处理的结点变成已经处理好的新头结点）
newHead = head;
// 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
head = next;
}
return newHead;
}
};
复制代码
c
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k){
struct ListNode *nextGroupHead = head;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
if (nextGroupHead == NULL) {
// 不够k就不用翻转了
return head;
}
nextGroupHead = nextGroupHead->next;
}
// 递归翻转后面
struct ListNode *newHead = reverseKGroup(nextGroupHead, k);
// 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
for (int i = 0; i < k; ++i) {
// 临时存放正在处理的结点的下一个结点
struct ListNode *next = head->next;
// 将正在处理的结点挂在新头的前面
head->next = newHead;
// 移动指针（正在处理的结点变成已经处理好的新头结点）
newHead = head;
// 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
head = next;
}
return newHead;
}
复制代码
python
# 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]:
next_group_head = head
# 查看剩余部分长度是否大于等于 k
for _ in range(k):
if next_group_head is None:
# 不够k就不用翻转了
return head
next_group_head = next_group_head.next
# 递归翻转后面
new_head = self.reverseKGroup(next_group_head, k)
# 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
for _ in range(k):
# 临时存放正在处理的结点的下一个结点
next = head.next
# 将正在处理的结点挂在新头的前面
head.next = new_head
# 移动指针（正在处理的结点变成已经处理好的新头结点）
new_head = head
# 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
head = next
return new_head
复制代码
java
/**
* 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 nextGroupHead = head;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
if (nextGroupHead == null) {
// 不够k就不用翻转了
return head;
}
nextGroupHead = nextGroupHead.next;
}
// 递归翻转后面
ListNode newHead = reverseKGroup(nextGroupHead, k);
// 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
for (int i = 0; i < k; ++i) {
// 临时存放正在处理的结点的下一个结点
ListNode next = head.next;
// 将正在处理的结点挂在新头的前面
head.next = newHead;
// 移动指针（正在处理的结点变成已经处理好的新头结点）
newHead = head;
// 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
head = next;
}
return newHead;
}
}
复制代码
/**
* 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 pre = dummy;
while (pre.next != null) {
ListNode tail = pre;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
tail = tail.next;
if (tail == null) {
return dummy.next;
}
}
// 指针后移
pre = reverse(pre, tail);
}
return dummy.next;
}
private ListNode reverse(ListNode pre, ListNode tail) {
ListNode newTail = pre.next;
ListNode newHead = tail.next;
ListNode head = newTail;
while (newHead != tail) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
pre.next = newHead;
return newTail;
}
}
复制代码
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://juejin.cn/user/2771185768884824/posts 博客原创~
开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 29 天，点击查看活动详情
|