[LeetCode] Reverse Nodes in k-Group

 

 

Problem

 

 

---

 

Solution

 

# 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]:
        # jump is always at the tail of the previous group
        # When reversing is complete in the next group,
        # jump.next points to that group's head
        # and jump moves to the tail of the new group
        # This way, current group's tail is always updated so that
        # it connects to the next group's head
        dummy = jump = ListNode(0)
        
        # l and r points to the start and end of current group
        l = r = dummy.next = head
        
        while True:
            count = 0
            # use r to locate range
            # l is the start of the group
            while r and count < k:
                count += 1
                r = r.next
            
            # if size k is satisfied, reverse inner list
            if count == k:
                # Go through the list with curr and pre
                # Make head(curr's initial position) point to the head of next group (pre's initial position)
                # and everything else should point backwards
                curr, pre = l, r
                
                for _ in range(k):
                    curr.next, curr, pre = pre, curr.next, curr
                
            # connect the groups
            # pre ends up in the head of the reversed list,
            # so make jump.next be that one
            # original list's head, l, will be the tail now
            # so jump is l
            # and update l so that it is the start of the next range(r's position)
                jump.next, jump, l = pre, l, r
            
            else:
                return dummy.next

Practice standard reversing of linked list (in place)

Pay attention to how jump is handled

 

Time Complexity

O(N)

 

 

Space Complexity

O(1)