# Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

`Input:  1---2---3---4---5---6--NULL                          |                          7---8---9---10--NULL                                  |                                  11--12--NULL Output: 1-2-3-7-8-11-12-9-10-4-5-6-NULL `
``````"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""

class Solution:
def flatten(self, head: 'Node') -> 'Node':
return None

stack = list()

while cur:
if cur.child:
if cur.next:
stack += [cur.next]
cur.next = cur.child
cur.next.prev = cur
cur.child = None

if not cur.next and stack:
temp = stack.pop()
cur.next = temp
temp.prev = cur

cur = cur.next

# Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

`    1       / \     2   5   / \   \ 3   4   6 `

The flattened tree should look like:

`1   \     2       \         3           \            4               \                 5         \                     6`
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
node, stack = root, []

while node:
if node.right:
stack.append(node.right)
node.right = node.left
node.left = None

if not node.right and stack:
temp = stack.pop()
node.right = temp

node = node.right``````

Example:

```Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
```

A linked list can be reversed either iteratively or recursively. Could you implement both?

As you can seen that recursion implementation is pretty easy to achieve, but iteratively achievement might not. Above are two implementations.

``````# iteratively
class Solution(object):
"""
:rtype: ListNode
"""
return None

while pionner.next:
pionner.next = pionner.next.next

``# recursively``

# Daily Temperatures

Given a list of daily temperatures `T`, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put `0` instead.

For example, given the list of temperatures `T = [73, 74, 75, 71, 69, 72, 76, 73]`, your output should be `[1, 1, 4, 2, 1, 1, 0, 0]`.

Note: The length of `temperatures` will be in the range `[1, 30000]`. Each temperature will be an integer in the range `[30, 100]`.

Solution:
This quiz is a classical application of the stack data structure. Here we can store indexes of each element which is waiting a bigger element in a stack, and calculate the difference between the current index and stored indexes when the current element is bigger than previous elements. The while loop part is really elegant and tricky, in which judging whether the stack is empty and comparing elements.

``````class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
ans = [0] * len(T)

stk = list()

for c_index, value in enumerate(T):
while stk and T[stk[-1]] < value:
p_index = stk.pop()
ans[p_index] = c_index - p_index
stk.append(c_index)

return ans``````

# Circular Queue

``````class MyCircularQueue:

def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the queue to be k.
"""
self.tail = -1
self.size = k
self.queue = [None] * self.size

def enQueue(self, value: int) -> bool:
"""
Insert an element into the circular queue. Return true if the operation is successful.
"""
if self.isFull():
return False

if self.isEmpty():

self.tail = (self.tail + 1) % self.size
self.queue[self.tail] = value
return True

def deQueue(self) -> bool:
"""
Delete an element from the circular queue. Return true if the operation is successful.
"""
if self.isEmpty():
return False

self.tail = -1
return True

return True

def Front(self) -> int:
"""
Get the front item from the queue.
"""
if self.isEmpty():
return -1

def Rear(self) -> int:
"""
Get the last item from the queue.
"""
if self.isEmpty():
return -1

return self.queue[self.tail]

def isEmpty(self) -> bool:
"""
Checks whether the circular queue is empty or not.
"""

def isFull(self) -> bool:
"""
Checks whether the circular queue is full or not.
"""
return (self.tail + 1) % self.size == self.head``````