都是O(n)
第一种逐层
1->2->11->12
|
3->4->5
|
6->7
1-2-11-12->3-4-5->6-7
static void flattenList(Node node) {
/*Base case*/
if (node == null) {
return;
}
Node tmp = null;
/* Find tail node of first level linked list */
Node tail = node;
while (tail.next != null) {
tail = tail.next;
}
// linked list till we reach the tail node
Node cur = node;
while (cur != tail) {
// If current node has a child
if (cur.child != null) {
// then append the child at the end of current list
tail.next = cur.child;
// and update the tail to new last node
tmp = cur.child;
while (tmp.next != null) {
tmp = tmp.next;
}
tail = tmp;
cur.child = null;
}
// Change current node
cur = cur.next;
}
}
第二种中间插入，使用栈
1->2->11->12
|
3->4->5
|
6->7
1-2-3-4-6-7-5-11-12
static void flattenList(Node node) {
if (node == null) {
return null;
}
Stack<Node> st = new Stack<>();
Node cur = node;
while (cur != null) {
if (cur.child != null) {
Node child = cur.child;
cur.child = null;
st.push(cur.next);
cur.next = child;
}
if (cur.next == null && !st.isEmpty()) {
cur.next = st.pop();
}
cur = cur.next;
}
}
