LC25. 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.

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.

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

General idea

We will need to iterate through the linked list k at a time. We will use : … 4 -> 5 -> 6 -> 7 -> 8 -> … k = 3, and the group starts at 5 as an example

  1. If we hit null before we got group of size k, we will not do anything.
  2. Else we go to 3
  3. Get the pointer to the node right before the beginning of the first node in group. let’s call it prev_ptr. In our example, we need to keep a pointer to 4.
  4. Get the pointer to the current node, cur_ptr. In our example, a pointer to 5.
  5. Reverse the linked list starting from current pointer ( in our case it is a pointer to 5), till k node after.
  6. Get the pointer to the first node in the reversed linked list, new_head. It should be returned by the reverse routine.
  7. Point prev_ptr to new_head and cur_ptr.next to Null
  8. Call this function again with head = curr.next

A refined and more concise general idea

While we have size k group :

  1. Move forward k group to find the head of next group ( might be less than k)
  2. Reverse size k linked list from head
  3. Connect the two groups

Code

    def reverseKGroup(self, head, k):
        dummy = jump = ListNode(0)
        dummy.next = l = r = head

        while True:
            count = 0
            while r and count < k:   # use r to locate the range
                r = r.next
                count += 1

            if count == k:  # if size k satisfied, reverse the inner linked list
                pre, cur = r, l
                for _ in range(k):
                    next_node = cur.next
                    cur.next = pre
                    pre = cur
                    cur = next_node

                jump.next, jump, l = pre, l, r  # connect two k-groups
                #print(jump.next.val, jump.val, l.val)
            else:
                return dummy.next

The outer while loop will be terminated when the number of remaining nodes starting from r is fewer than k.

After the while loop that move r forward, r will point at the head of next group.

At the end of for loop, pre will contain the tail of the last group. Since the group is reversed, pre will contain the head of the reversed list.

jump is the tail of the old group. We will point jump.next it at the head of the next group, which is pre.

In the next iteration, the tail of the previous reversed group is the head of the previous unreversed group. So we point jump at l at each round.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax