Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/25.html
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.
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]
Constraints:
- The number of nodes in the list is
n
. 1 <= k <= n <= 5000
0 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1)
extra memory space?
Algorithm
To reverse a linked list in groups of size k
, we first need to divide the original linked list into several small segments, each containing k
nodes, and then flip each segment separately. This requires two functions, one for segmentation and one for flipping.
For example, consider the linked list 1->2->3->4->5
. When dealing with linked list problems, it’s common to add a dummy node at the beginning because the head node may change when the linked list is flipped. To keep track of the current latest position of the head node, we introduce a dummy node before the original head node. In this case, the linked list after adding the dummy node becomes -1->1->2->3->4->5
.
To reverse the group of nodes 1, 2, and 3 when k
is 3, we need two pointers: pre
and next
. pre
points to the node before the group to be flipped, and next
points to the node after the group to be flipped. After flipping the group, the position of pre
is updated to the following new position.
prev
is dummy, then current
is always node ‘1’, ‘1’ will move each iteration of while loop for k-group swap
prev
is static during the full while loop of while (kcopy > 0)
1->2->3->4->5 , k=3
2,1,3,4,5
3,2,1,4,5
=> always getting 1's next for prev's next => current (below) not changing in one-batch-swap
Code
-
public class Reverse_Nodes_in_k_Group { class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; // count total nodes ListNode tmp = head; int count = 0; while (tmp != null) { count++; tmp = tmp.next; } // 1->2->3->4->5 , k=3 // 2,1,3,4,5 // 3,2,1,4,5 // => always getting 1's next for prev's next => current (below) not changing in one-batch-swap // if only one node left, then no swap while (count >= k) { ListNode originalFirst = prev.next; int kcopy = k - 1; // @note: since current node is already counted as 1 while (kcopy > 0) { // both prev and current, not changed in while loop ListNode nextNextCopy = originalFirst.next.next; ListNode firstInGroup = prev.next; prev.next = originalFirst.next; prev.next.next = firstInGroup; originalFirst.next = nextNextCopy; kcopy--; } // @note: update previous AND current. I forgot current... prev = originalFirst; // now current is the last one of this group count -= k; } return dummy.next; } } }
-
// OJ: https://leetcode.com/problems/reverse-nodes-in-k-group/ // Time: O(N) // Space: O(1) class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode h, *tail = &h; while (head) { auto prev = tail; int i = 0; for (auto p = head; i < k && p; ++i, p = p->next); if (i < k) { tail->next = head; break; } for (int i = 0; i < k && head; ++i) { auto node = head; head = head->next; node->next = prev->next; prev->next = node; } while (tail->next) tail = tail->next; } return h.next; } };
-
# 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: def reverseList(head): pre, p = None, head while p: q = p.next p.next = pre pre = p p = q return pre dummy = ListNode(next=head) pre = cur = dummy while cur.next: for _ in range(k): cur = cur.next if cur is None: return dummy.next t = cur.next cur.next = None # cut from next k-group, so to reverseList() for current k-group start = pre.next pre.next = reverseList(start) start.next = t # so now 'start' is the last node of k-group pre = cur = start # same as the reset before while loop return dummy.next ############ # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseKGroup(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ def reverseList(head, k): pre = None cur = head while cur and k > 0: tmp = cur.next cur.next = pre pre = cur cur = tmp k -= 1 head.next = cur return cur, pre length = 0 p = head while p: length += 1 p = p.next if length < k: return head step = length / k ret = None pre = None p = head while p and step: next, newHead = reverseList(p, k) if ret is None: ret = newHead if pre: pre.next = newHead pre = p p = next step -= 1 return ret
-
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseKGroup(head *ListNode, k int) *ListNode { start, end := head, head for i := 0; i < k; i++ { if end == nil { return head } end = end.Next } res := reverse(start, end) start.Next = reverseKGroup(end, k) return res } func reverse(start, end *ListNode) *ListNode { var pre *ListNode = nil for start != end { tmp := start.Next start.Next, pre = pre, start start = tmp } return pre }
-
/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function reverseKGroup(head: ListNode | null, k: number): ListNode | null { let dummy = new ListNode(0, head); let pre = dummy; // pre->head-> ... ->tail-> next while (head != null) { let tail = pre; for (let i = 0; i < k; ++i) { tail = tail.next; if (tail == null) { return dummy.next; } } let t = tail.next; [head, tail] = reverse(head, tail); // set next pre.next = head; tail.next = t; // set new pre and new head pre = tail; head = t; } return dummy.next; } function reverse(head: ListNode, tail: ListNode) { let cur = head; let pre = tail.next; // head -> next -> ... -> tail -> pre while (pre != tail) { let t = cur.next; cur.next = pre; pre = cur; cur = t; } return [tail, head]; }
-
/** * 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) { ListNode dummy = new ListNode(0, head); ListNode pre = dummy, cur = dummy; while (cur.next != null) { for (int i = 0; i < k && cur != null; ++i) { cur = cur.next; } if (cur == null) { return dummy.next; } ListNode t = cur.next; cur.next = null; ListNode start = pre.next; pre.next = ReverseList(start); start.next = t; pre = start; cur = pre; } return dummy.next; } private ListNode ReverseList(ListNode head) { ListNode pre = null, p = head; while (p != null) { ListNode q = p.next; p.next = pre; pre = p; p = q; } return pre; } }