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--NULLOutput:1-2-3-7-8-11-12-9-10-4-5-6-NULL
Explanation for the above example:
Given the following multilevel doubly linked list:
We should return the following flattened doubly linked list:
M1: straight forward
用一个pointer遍历linked list，遇到有child的节点，就把整个child linked list加入linked list，再继续遍历，直到走到null为止
time: O(n) -- n: total # of nodes, space: O(1)
/*// Definition for a Node.class Node { public int val; public Node prev; public Node next; public Node child; public Node() {} public Node(int _val,Node _prev,Node _next,Node _child) { val = _val; prev = _prev; next = _next; child = _child; }};*/class Solution { public Node flatten(Node head) { if(head == null) { return head; } Node cur = head; while(cur != null) { if(cur.child == null) { cur = cur.next; continue; } Node childTail = cur.child; while(childTail.next != null) { childTail = childTail.next; } if(cur.next != null) { cur.next.prev = childTail; } childTail.next = cur.next; cur.next = cur.child; cur.child.prev = cur; cur.child = null; cur = cur.next; } return head; }}
M2: recursion, dfs
1. head = null，或者只有head一个节点，没next/child，return；
2. 没child, next；
3. 有child，没next，flatten即可；
4. 有child，有next，flatten完，把cur.next和child的tail连接起来
time: O(n) -- n: total # of nodes, space: O(k) -- k: total # of child
/*// Definition for a Node.class Node { public int val; public Node prev; public Node next; public Node child; public Node() {} public Node(int _val,Node _prev,Node _next,Node _child) { val = _val; prev = _prev; next = _next; child = _child; }};*/class Solution { public Node flatten(Node head) { dfs(head); return head; } private Node dfs(Node head) { if(head == null) { return head; } else if(head.child == null) { if(head.next == null) { return head; } return dfs(head.next); } else { Node child = head.child; head.child = null; Node next = head.next; Node childTail = dfs(child); head.next = child; child.prev = head; if(next != null) { childTail.next = next; next.prev = childTail; return dfs(next); } return childTail; } }}