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

25 - Reverse Nodes in k-Group

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions