Code & Func
2019-12-19

第43天。

今天的题目是Flatten a Multilevel Doubly Linked List:

蛮好玩的一道题。

本来想用递归做的,但是发现好像需要一层一层的返回最后一个指针,觉得有点麻烦,就直接用栈做了。

这个栈是用来保存上一层的指针的,而且看起来每一层最多一个节点有child,所以我们可以这样做:

  • 遍历当前层,如果有孩子,则把当前节点压入栈中,并跳到下一层去遍历
  • 如果遍历完当前层,则从栈中取出parent,然后进行flatten,为了避免没有必要的重复遍历,当前层最后一个节点压入栈中,这样下一次遍历时,就从上一层中第一个未被遍历的节点开始了。

代码如下:

1
Node* flatten(Node* head) {
2
if (head == nullptr) return nullptr;
3
stack<Node*> st;
4
st.push(head);
5
// if (head->child) st.push(head->child);
6
while(!st.empty()) {
7
Node *p = st.top(); st.pop();
8
while(!p->child && p->next) {
9
p = p->next;
10
}
11
if (p->child) {
12
st.push(p);
13
st.push(p->child);
14
} else if (!st.empty()) {
15
Node *parent = st.top(); st.pop();
10 collapsed lines
16
p->next = parent->next;
17
if (p->next) p->next->prev = p;
18
parent->next = parent->child;
19
parent->next->prev = parent;
20
parent->child = nullptr;
21
st.push(p);
22
}
23
}
24
return head;
25
}
上一条动态