25. Reverse Nodes in k-Group
給定一個鏈表的頭節點，每次翻轉鏈表的 k 個節點，並返回修改後的鏈表。
k 是一個正整數，並且小於或等於鏈表的長度。如果節點的數量不是 k 的倍數，則最後剩餘的節點應保持不變。
你不能改變鏈表中節點的值，只能改變節點本身。
Python
from typing import Optional
# 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]:
# Helper function to reverse a linked list
def reverseLinkedList(head: ListNode, k: int) -> ListNode:
new_head = None
ptr = head
while k > 0:
next_node = ptr.next
ptr.next = new_head
new_head = ptr
ptr = next_node
k -= 1
return new_head
# Check the length of the list
count = 0
ptr = head
while ptr and count < k:
ptr = ptr.next
count += 1
# If the number of nodes is less than k, return the head as it is
if count < k:
return head
# Reverse the first k nodes
new_head = reverseLinkedList(head, k)
# Recursively process the remaining nodes
if head:
head.next = self.reverseKGroup(ptr, k)
return new_head
17.39MB, 55ms
C++
/**
* 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) {
// Helper function to reverse a linked list
auto reverseLinkedList = [](ListNode* head, int k) -> ListNode* {
ListNode* new_head = nullptr;
ListNode* ptr = head;
while (k > 0) {
ListNode* next_node = ptr->next;
ptr->next = new_head;
new_head = ptr;
ptr = next_node;
k--;
}
return new_head;
};
// Check the length of the list
int count = 0;
ListNode* ptr = head;
while (ptr && count < k) {
ptr = ptr->next;
count++;
}
// If the number of nodes is less than k, return the head as it is
if (count < k) {
return head;
}
// Reverse the first k nodes
ListNode* new_head = reverseLinkedList(head, k);
// Recursively process the remaining nodes
if (head) {
head->next = reverseKGroup(ptr, k);
}
return new_head;
}
};
15.01MB, 7ms
Javascript
/**
* 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) {
// Helper function to reverse a portion of the linked list
const reverseLinkedList = (head, k) => {
let newHead = null;
let ptr = head;
while (k > 0) {
let nextNode = ptr.next;
ptr.next = newHead;
newHead = ptr;
ptr = nextNode;
k--;
}
return newHead;
};
// Check the length of the list
let count = 0;
let ptr = head;
while (ptr && count < k) {
ptr = ptr.next;
count++;
}
// If the number of nodes is less than k, return the head as it is
if (count < k) {
return head;
}
// Reverse the first k nodes
let newHead = reverseLinkedList(head, k);
// Recursively process the remaining nodes
if (head) {
head.next = reverseKGroup(ptr, k);
}
return newHead;
};
51.81MB, 71ms
