Consider this interview question:
Given a Node with a reference to a child, its next, its previous, and a variable for its value (\$\frac{1}{2}\$ tree, \$\frac{1}{2}\$ doubly linked list structure), you have to find a way to flatten the structure.
1 = 2 = 3 = 5 | | 6 = 7 8 | 9
(reference down is child and reference across is next)
this above diagram becomes: 1 - 2 - 6 - 7- 9 - 3 - 5 - 8 but:
- 2 still has child reference to 6
- 7 still has child reference to 9
- 5 still has child reference to 8
Here is my code:
class Node(object):
def __init__(self, value, next_node=None, prev=None, child=None):
self.value = value
self.next = next_node
self.prev = prev
self.child = child
def __repr__(self):
return str(self.value)
one = Node(1)
two = Node(2)
three = Node(3)
five = Node(5)
six = Node(6)
seven = Node(7)
eight = Node(8)
nine = Node(9)
one.next = two
two.prev = one
two.next = three
two.child = six
three.prev = two
three.next = five
five.prev = three
five.child = eight
six.next = seven
seven.prev = six
seven.child = nine
def flatten(head):
if not head: return head
c = flatten(head.child)
n = flatten(head.next)
if c:
head.next = head.child
head.child.prev = head
if c and n:
tail = c
while tail.next:
tail = tail.next
tail.next = n
n.prev = tail
return head
n = flatten(one)
while n:
print "%d -" % (n.value,),
n = n.next
I don't like the while loop. I could store tail and pass it around. Any better solution?
Node
class to handle the fact that wheni.next
isj
thenj.prev
isi
in order not to have to set the two relations manually. \$\endgroup\$link
function. \$\endgroup\$