Lenghy python code for K lists with circular doubly linked list


  • 0
    Y

    Time complexity: O(1)
    Space complexity: O(K)

    class DLNode(object):
        def __init__(self,arr):
            self.offset=0
            self.arr=arr
            self.next=None
            self.prev=None
    
    class ZigzagIterator(object):
    
        def __init__(self, v1, v2):
            """
            Initialize your data structure here.
            :type v1: List[int]
            :type v2: List[int]
            """
            head,tail=DLNode([]),DLNode([])
            head.next=tail
            tail.prev=head
            self.size=0
            for v in [v1,v2]:
                if len(v):
                    node=DLNode(v)
                    tail.prev.next=node
                    node.prev=tail.prev
                    node.next=tail
                    tail.prev=node
                    self.size+=1
            self.cur=head.next
            head.next.prev=tail.prev
            tail.prev.next=head.next
            
    
        def next(self):
            """
            :rtype: int
            """
            n=self.cur
            self.cur=self.cur.next
            res=n.arr[n.offset]
            n.offset+=1
            if n.offset==len(n.arr):
                n.prev.next=n.next
                n.next.prev=n.prev
                self.size-=1
            return res
    
        def hasNext(self):
            """
            :rtype: bool
            """
            return self.size>0
            
    
    # Your ZigzagIterator object will be instantiated and called as such:
    # i, v = ZigzagIterator(v1, v2), []
    # while i.hasNext(): v.append(i.next())
    
    

Log in to reply
 

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