Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/25.html
25 Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified 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 nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
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
Java
-
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 start = pre.next pre.next = reverseList(start) start.next = t pre = start cur = pre 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