Description:
Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.
You may not alter the values in the list’s nodes, only nodes themselves may be changed.
Examples:
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]Solution in Python:
To solve the problem of reversing the nodes of a linked list k at a time, we need to break the list into segments of k nodes and reverse each segment individually. If the number of nodes is not a multiple of k, the remaining nodes at the end should stay as they are.
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: ListNode, k: int) -> ListNode:
# Helper function to reverse a portion of the list
def reverse(start, end):
prev, curr = None, start
while curr != end:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
# Create a dummy node to handle edge cases easily
dummy = ListNode(0)
dummy.next = head
group_prev = dummy
while True:
kth = group_prev
# Find the k-th node from the current position
for i in range(k):
kth = kth.next
if not kth:
return dummy.next
group_next = kth.next
# Reverse the group of k nodes
prev, curr = kth.next, group_prev.next
for _ in range(k):
curr.next, prev, curr = prev, curr, curr.next
# Connect the reversed group to the previous part of the list
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
return dummy.nextDetailed Comments:
- ListNode Definition:
- The
ListNodeclass defines a node in a linked list, with a value (val) and a pointer to the next node (next).
- The
- Helper Function:
reverse(start, end)is a helper function to reverse a portion of the list fromstartup to but not includingend.- Inside the helper function, we iterate through the nodes, reversing their pointers until we reach the
end.
- Dummy Node Initialization:
- A dummy node (
ListNode(0)) is created and points to the head of the list. This helps in handling edge cases where the list length is less than k and simplifies the pointer manipulations. dummy.next = headensures the dummy node is linked to the head of the input list.
- A dummy node (
- Main Loop:
- We use
group_prevto keep track of the node before the current group of k nodes that we are reversing. - The
while Trueloop continues to process the list in segments of k nodes. kth = group_previs used to find the k-th node from the current position.- If we can’t find k nodes (
if not kth), we return the list as it is, because the remaining nodes are fewer than k. group_next = kth.nextsaves the node right after the k-th node to reconnect after reversing the group.- We reverse the k nodes using a loop that iterates k times.
- After reversing, we reconnect the reversed group to the rest of the list by adjusting the
nextpointers ofgroup_prevandtmp(the node that was at the beginning of the group before reversal).
- We use
- Return the Modified List:
- Finally, we return the new head of the modified list, which is
dummy.next.
- Finally, we return the new head of the modified list, which is
This approach ensures that we only change the pointers of the nodes and not their values, which is required by the problem constraints. The time complexity of this solution is O(N), where N is the number of nodes in the linked list, as we traverse the list multiple times but in a controlled manner.
Solution in Javascript:
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 list
function reverse(start, end) {
let prev = null;
let curr = start;
while (curr !== end) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
// Create a dummy node to handle edge cases easily
let dummy = new ListNode(0);
dummy.next = head;
let groupPrev = dummy;
while (true) {
let kth = groupPrev;
// Find the k-th node from the current position
for (let i = 0; i < k; i++) {
kth = kth.next;
if (!kth) {
return dummy.next;
}
}
let groupNext = kth.next;
// Reverse the group of k nodes
let prev = kth.next;
let curr = groupPrev.next;
for (let i = 0; i < k; i++) {
let nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
// Connect the reversed group to the previous part of the list
let temp = groupPrev.next;
groupPrev.next = kth;
groupPrev = temp;
}
return dummy.next;
};Solution in Java:
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) {
if (head == null || k == 1) {
return head; // No need to process if head is null or k is 1
}
// Create a dummy node to handle edge cases easily
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize pointers
ListNode curr = head;
ListNode prevGroupEnd = dummy;
ListNode nextGroupStart = null;
while (curr != null) {
// Check if there are at least k nodes left to reverse
ListNode temp = curr;
for (int i = 0; i < k; i++) {
if (temp == null) {
return dummy.next; // Not enough nodes to reverse, return result
}
temp = temp.next;
}
// Reverse k nodes
ListNode prev = null;
ListNode tail = curr;
for (int i = 0; i < k; i++) {
nextGroupStart = curr.next;
curr.next = prev;
prev = curr;
curr = nextGroupStart;
}
// Connect the previous part with the reversed segment
prevGroupEnd.next = prev;
tail.next = nextGroupStart;
// Move prevGroupEnd to the end of the newly reversed segment
prevGroupEnd = tail;
}
return dummy.next;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head; // No need to process if head is null or k is 1
}
// Create a dummy node to handle edge cases easily
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize pointers
ListNode curr = head;
ListNode prevGroupEnd = dummy;
ListNode nextGroupStart = null;
while (curr != null) {
// Check if there are at least k nodes left to reverse
ListNode temp = curr;
for (int i = 0; i < k; i++) {
if (temp == null) {
return dummy.next; // Not enough nodes to reverse, return result
}
temp = temp.next;
}
// Reverse k nodes
ListNode prev = null;
ListNode tail = curr;
for (int i = 0; i < k; i++) {
nextGroupStart = curr.next;
curr.next = prev;
prev = curr;
curr = nextGroupStart;
}
// Connect the previous part with the reversed segment
prevGroupEnd.next = prev;
tail.next = nextGroupStart;
// Move prevGroupEnd to the end of the newly reversed segment
prevGroupEnd = tail;
}
return dummy.next;
}
}