[Leetcode] 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.

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

There is nothing tricky in the question. You just need to think it carefully and code it up...It feels overwhelming, but there is two points to think through:

1. What to record?
2. How to reverse a linked list given two ends?

For the first question, think about the example 4 --> 5 --> 3 --> 2 --> 1, k = 2, and the end result will be 5 --> 4 --> 2 --> 3 --> 1. Basically, we need to know when to start reversing, when to end, and in order to connect the previous piece, we also need another pointer from previous piece.

The second question is just some tricky linked list manipulation: we have a p_prev to record the previous node, and p to record the current node. When we sweeping over the p, we just point the p to p_prev and then make p as p_pre.

My code below is kinda ugly --- too long, but idea is there.

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

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k == 1:
            return head
        def reverse(h, t):
            p_prev = h
            p = h.next
            while p != t:
                p_next = p.next
                p.next = p_prev
                p_prev, p = p, p_next
            p.next = p_prev
            
        aux = ListNode(0)
        aux.next = head
        p = head
        i = 0
        prev = aux
        while p:
            if i % k == 0:
                tmp_head = p
                p = p.next
            elif i % k == k -1:
                p_next = p.next
                tmp_tail = p
                reverse(tmp_head, tmp_tail)
                tmp_head.next = p_next
                prev.next = tmp_tail
                prev = tmp_head
                p = p_next
            else:
                p = p.next
            i += 1
        return aux.next