Recursive and iterative python using with k-size list


  • 0
    Z

    I know one can manipulate the pointers to solve this problem, for me an additional list would be way easier to handle.. list length is k, I believe still "constant"..(correct me if I am wrong) Both recursive and iterative are pretty fast, usually take less than 80 ms

    recursive:

    def reverseKGroup(self, head, k):
        return self.revK(head, k, [])
    
    def revK(self, head, k, prev):
        oldhead = head
        buff = [0 for x in range(k)]
        for i in range(k):
            if head:
                buff[i] = head
                head = head.next
            else: return oldhead
        for i in range(k-1):
            buff[i+1].next = buff[i]
        if prev:
            prev.next = buff[-1]
        buff[0].next = head # head is in the next k group
        self.revK(buff[0].next, k, buff[0])
        return buff[-1]
    

    iterative:

    def reverseKGroup(self, head, k):
        newhead,prev = head,[]
        buff = [0 for x in range(k)]
    
        while head:
            for i in range(k):
                if head:
                    buff[i] = head
                    head = head.next
                else:
                    return newhead
            for i in range(k-1):
                buff[i+1].next = buff[i]
            if prev:
                prev.next = buff[-1]    # since 2nd iteration, there is prev
            else:
                newhead = buff[-1]      # in 1st iteration, there is no prev
            buff[0].next = head # head is in the next k group
            prev = buff[0]
        return newhead

Log in to reply
 

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