1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public Node flatten(Node head) {
if (head == null) {
return null;
}
Node senital = new Node();
helper(senital, head);
head.prev = null;
return head;
}
private Node helper(Node prevNode, Node currNode) {
if (currNode == null) {
return prevNode;
}
prevNode.next = currNode;
currNode.prev = prevNode;
prevNode = currNode;
Node nextNode = currNode.next;
if (currNode.child != null) {
prevNode = helper(prevNode, currNode.child);
currNode.child = null;
}
return helper(prevNode, nextNode);
}
}
|
这道题的启示就是要弄清递归函数在干嘛. 这里定义的递归函数的定义就是给定的currNode及其以后的node都会被flattened并且返回给我们这个list的最后一个node. 同时currNode的prev也会指向我们传递的prevNode这个参数.
时间复杂度: O(n)
空间复杂度: O(n)
