Leetcode
2020.04.06 17:12

# 430. Flatten a Multilevel Doubly Linked List

조회 수 214 추천 수 0 댓글 0
?

#### 단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부
?

#### 단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 첨부

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 1:

```Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

```

Example 2:

```Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

1---2---NULL
|
3---NULL
```

Example 3:

```Input: head = []
Output: []
```

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

``` 1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL```

The serialization of each level is as follows:

```[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
```

To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

```[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
```

Merging the serialization of each level and removing trailing nulls we obtain:

`[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]`

Constraints:

• Number of Nodes will not exceed 1000.
• `1 <= Node.val <= 10^5`

```/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/

class Solution {
Node result;
Node current;

result = new Node(-1);
current = result;

return result.next;
}

if (node == null) {
return;
}

Node prev = current;
current.next = new Node(node.val);
current = current.next;
current.prev = prev.val == -1 ? null : prev;

if (node.child != null) {
}

}
}```

?

 제목+내용제목내용댓글이름닉네임아이디태그
List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
17 Leetcode 287. Find the Duplicate Number 2020.04.16 211
16 Leetcode 253. Meeting Rooms II 2020.04.15 211
15 Leetcode 731. My Calendar II 2020.04.15 194
14 Leetcode 729. My Calendar I 2020.04.15 187
13 Leetcode 692. Top K Frequent Words 2020.04.15 195
12 Leetcode 973. K Closest Points to Origin 2020.04.15 210
11 Leetcode 75. Sort Colors 2020.04.14 184
10 Leetcode 2. Add Two Numbers 2020.04.14 194
9 Leetcode 23. Merge k Sorted Lists 2020.04.14 204
8 Leetcode 347. Top K Frequent Elements 2020.04.14 196
7 Leetcode 994. Rotting Oranges 2020.04.14 212
6 Leetcode 3. Longest Substring Without Repeating Characters 2020.04.09 209
5 Leetcode 62. Unique Paths 2020.04.09 206
4 Leetcode 946. Validate Stack Sequences 2020.04.08 194
3 Leetcode 114. Flatten Binary Tree to Linked List 2020.04.06 216
» Leetcode 430. Flatten a Multilevel Doubly Linked List 2020.04.06 214
1 Leetcode 1055. Shortest Way to Form String 2020.04.06 251
Board Pagination Prev 1 2 3 4 Next
/ 4