Short Python O(n) time and O(1) space


  • 0

    First find n which represent total number of nodes, then do n//k times reverse processes. Remember to re-initialize pre and p before the next reverse process.

    class Solution(object):
        def reverseKGroup(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            dummy = p = ListNode(0)
            dummy.next = head
            n = 0
            while p.next:                   # find how many nodes we have in total
                p = p.next
                n += 1
            pre, p = dummy, dummy.next
            for j in range(n//k):           # we need n//k times reverse processes
                for i in range(k-1):
                    pre.next, p.next, pre.next.next = p.next, p.next.next, pre.next
                pre, p = p, p.next          # set new "pre" and "p" node
            return dummy.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.