Reverse Nodes in k-Group

Problem Id: 25 Difficulty: Hard Tag: Linked List


Intuition

To make the problem simpler, let's split the problem and solve it by 3 steps:

  1. Split the sub-list which need to be reversed.
  2. Reverse the sub-list.
  3. Add the reversed list to to the overall list.

For the big list, we will need several pointers which looks like below. Suppose k = 3

               before start     end after
                  |    |         |    |
head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

For the sub list, we need 2 pointers to reverse it.

prev  curr
  |    |
  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

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: ListNode, k: int) -> ListNode:
        head = ListNode(None, next=head)
        before = head
        start = head.next

        while True:
            end = start
            for _ in range(k - 1):
                if end is None:
                    break
                end = end.next

            if end is None:
                break
            after = end.next
            end.next = None
            start, end = self._reverse(start)
            before.next = start
            end.next = after
            start = after
            before = end
        return head.next

    def _reverse(self, head):
        """reverse the given linked list and return the first and last node
        of the reversed linked list"""
        prev = None
        curr = head
        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
        return prev, head