0025-reverse-nodes-in-k-group¶

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.

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?

Solution(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: Optional[ListNode], k: int) -> Optional[ListNode]:
        # case k < n
        #       leftover = n%k   
        #       multiple m//k
        #   total = multiple * k + leftover 
        #   1.1   index < leftover  reverse 
        #            sublist 1 start  ....sublist 1 end ....  sublist 2 start  ....sublist 2 end
        #             
        #            sublist 1 end ........sublist 1 start ... sublist 2 end .........sublist 2 start 
        #           prevstart .next = curend
        #    1.2    index > leftover  keep it as it is
        #    
        #     
        # case k >= n 
        #      reverse whole list
        #  for isolated segment
        #  1 2 3
        #    k =3 
        # prev = None
        # cur = head 
        # for _ in range(k):
        #    nct = cur.next
        #    cur.next = prev 
        #    prev = cur
        #    cur = nxt
        #  prev = new head 
        #  cur = end
        # 1 2 3 
        # prev = None cur =1
        # nxt = 2 ; 1 -> None 
        # prev = 1, cur = 2
        # nxt = 3 ; 2 -> 1 -> None
        # prev = 2 , cur = 3
        # nxt = None
        # 3 -> 2 -> 1 ->None
        # prev = 3
        # cur = None
        # stitiching
        #  before reverseing group save group_prev , group_start 
        # 
        # ---- Phase 1: count nodes ----
            # length ← count of nodes in the list
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

    # # ---- Phase 2: setup ----
    # create dummy node pointing to head
    # previous_group_end ← dummy
        dummy = ListNode(0, head)
        previous_group_end  = dummy


    # ---- Phase 3: process each full group ----
        for _ in range(length//k):
             # 3a. locate the end of this group
            group_end  = previous_group_end 
            for _ in range(k):
                group_end  = group_end.next
            
            # node_after_group ← group_end.next
            node_after_group  = group_end.next
            new_next = node_after_group 
            current = previous_group_end.next

            #  # 3b. reverse this group in place

            while current != node_after_group:
                next_node = current.next
                current.next = new_next
                new_next = current
                current = next_node
            # 3c. reconnect this group to the previous one
            old_group_head = previous_group_end.next
            previous_group_end.next = group_end 
            previous_group_end = old_group_head 


        return dummy.next

        