Flatten a Doubly-Linked List (Leetcode 8)

Isn’t this basically the same as the last one? Instead of left and right it’s “child” and “next”. The doubly-linked stitching is a bit different, but nothing major. Interesting contrast.

class Solution(object):
    def flatten(self, head):
        if head is None:
            return None
        if head.child is None:
            self.flatten(head.next)
            return head
        flatChild = self.flatten(head.child)
        head.child = None

        childEnd = flatChild
        while childEnd.next != None:
            childEnd = childEnd.next
        
        
        oldNext = head.next
        if oldNext:
            oldNext.prev = childEnd
        childEnd.next = oldNext

        flatChild.prev = head
        head.next = flatChild
        
        return head

Leave a Reply