共计 2358 个字符,预计需要花费 6 分钟才能阅读完成。
题目要求
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 |
思路一:递归实现深度优先遍历
从深度优先遍历的角度来看,每次遇到一个包含子节点中间双链表节点,就递归的调用展开方法将其展开,并将展开的结果插入到当前节点的后面。这里需要注意双链表前节点前后指针的变更。步骤如下:
Step1: | |
1---2---3---4---5---6--NULL | |
| | |
7---8---9---10--NULL | |
| | |
11--12--NULL | |
Step2: | |
1---2---3---4---5---6--NULL | |
| | |
7---8---11--12--9---10--NULL | |
Step3: | |
1---2---3---7---8---11--12--9---10--4---5---6--NULL |
代码如下:
public Node flatten(Node head) {if(head == null) return head; | |
Node tmp = head; | |
while(tmp != null) {if(tmp.child != null) {Node child = flatten(tmp.child); | |
tmp.child = null; | |
Node next = tmp.next; | |
tmp.next = child; | |
child.prev = tmp; | |
while(child.next != null) {child = child.next;} | |
child.next = next; | |
if(next != null) {next.prev = child;} | |
tmp = next; | |
}else {tmp = tmp.next;} | |
} | |
return head; | |
} |
思路二:循环
上面的思路同样可以通过循环的方式来解决。每遇到一个有子节点的双链表节点,就将其子节点的头和尾拼接到父节点的双链表上,使其看上去是一个新的双链表。再对双链表的下一个节点进行判断。基本步骤如下:
Step1: | |
1---2---3---4---5---6--NULL | |
| | |
7---8---9---10--NULL | |
| | |
11--12--NULL | |
Step2: | |
1---2---3---7---8---9---10---4---5---6--NULL | |
| | |
11--12--NULL | |
Step3: | |
1---2---3---7---8---11--12--9---10--4---5---6--NULL |
代码如下:
public Node flatten(Node head) {if(head == null) return null; | |
Node tmp = head; | |
while(tmp != null) {if(tmp.child != null) { | |
Node child = tmp.child; | |
tmp.child = null; | |
Node next = tmp.next; | |
tmp.next = child; | |
child.prev = tmp; | |
while(child.next != null) {child = child.next;} | |
if(next != null) { | |
child.next = next; | |
next.prev = child; | |
} | |
} | |
tmp = tmp.next; | |
} | |
return head; | |
} |
思路 3:减少遍历次数
之前的两种思路,都会出现大量的重复遍历,重复遍历和叶子节点的深度成正相关,可以想方法将重复遍历的次数减少。其实,我们可以看见,无论我们何时将子节点展开,并拼接回父节点的双链表中,子节点展开的双链表的头结点是固定的,并且可以用父节点访问到。而尾节点必须通过重复遍历来查找并拼接。因此,如果每次都将展开后的尾节点返回,就可以无需重复遍历将展开的子节点拼接回父节点。代码如下:
public Node flatten(Node head) {flattenAndReturnTail(head); | |
return head; | |
} | |
public Node flattenAndReturnTail(Node head) {if(head == null) return null; | |
if(head.child == null) {if(head.next == null) return head; | |
return flattenAndReturnTail(head.next); | |
}else { | |
Node child = head.child; | |
head.child = null; | |
Node next = head.next; | |
Node childTail = flatten(child); | |
head.next = child; | |
child.prev = head; | |
if(next != null) { | |
childTail.next = next; | |
next.prev = childTail; | |
return flattenAndReturnTail(next); | |
} | |
return childTail; | |
} | |
} |
正文完