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
    
    

All Problems

All Solutions