原題鏈接在這里：https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

題目：

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:

題解：

如果當(dāng)前點(diǎn)cur 沒(méi)有child, 直接跳到cur.next 進(jìn)行下次計(jì)算.

如果cur 有child, 目標(biāo)是把cur.child這個(gè)level提到cur這個(gè)level上. 至于cur.child 這個(gè)level上有沒(méi)有點(diǎn)有child 先不管.?

做法就是cur.child 一直只按next找到tail, 然后這一節(jié)插在cur 和 cur.next之間, cur再跳到更新的cur.next上.

Time Complexity: O(n). n是所有點(diǎn)的個(gè)數(shù), 每個(gè)點(diǎn)只走過(guò)constant次數(shù).

Space: O(1).

AC Java:

1 /* 2 // Definition for a Node. 3 class Node { 4 public int val; 5 public Node prev; 6 public Node next; 7 public Node child; 8 9 public Node() {} 10 11 public Node(int _val,Node _prev,Node _next,Node _child) { 12 val = _val; 13 prev = _prev; 14 next = _next; 15 child = _child; 16 } 17 }; 18 */ 19 class Solution { 20 public Node flatten(Node head) { 21 if(head == null){ 22 return head; 23 } 24 25 Node cur = head; 26 while(cur != null){ 27 if(cur.child == null){ 28 cur = cur.next; 29 continue; 30 } 31 32 Node child = cur.child; 33 Node childTail = child; 34 while(childTail.next != null){ 35 childTail = childTail.next; 36 } 37 38 cur.child = null; 39 child.prev = cur; 40 childTail.next = cur.next; 41 if(cur.next != null){ 42 cur.next.prev = childTail; 43 } 44 cur.next = child; 45 cur = cur.next; 46 } 47 48 return head; 49 } 50 }

類似Flatten Binary Tree to Linked List.

轉(zhuǎn)載于:https://www.cnblogs.com/Dylan-Java-NYC/p/9596026.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode 430. Flatten a Multilevel Doubly Linked List的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。