Reverse Nodes in k-Group

Question

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.

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

Tags

• Linked List

Thought

Composed by two parts:

1. Partition of the linked list based on counts
2. Reverse the linked list

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        if not head:
            return None
        tail, current, prev = head, head, None
        while current.next:
            next = current.next
            current.next = prev
            prev = current
            current = next
        current.next = prev
        return current, tail

    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        count = k
        ptr, prev = head, None
        while count > 0 and ptr:
            prev = ptr
            ptr = ptr.next
            count -= 1
        if count > 0:
            return head
        prev.next = None
        newHead, newTail = self.reverseList(head)
        newTail.next = self.reverseKGroup(ptr, k)
        return newHead