Leetcode
2020.04.06 17:12

# 430. Flatten a Multilevel Doubly Linked List

조회 수 98 추천 수 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;

public Node flatten(Node head) {
result = new Node(-1);
current = result;

return result.next;
}

private void addNodes(Node node) {
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
번호 분류 제목 글쓴이 날짜 조회 수
74 Leetcode 692. Top K Frequent Words 2020.04.15 87
73 Leetcode 2. Add Two Numbers 2020.04.14 90
72 Leetcode 731. My Calendar II 2020.04.15 94
71 Leetcode 75. Sort Colors 2020.04.14 95
70 Leetcode 347. Top K Frequent Elements 2020.04.14 96
» Leetcode 430. Flatten a Multilevel Doubly Linked List 2020.04.06 98
68 Leetcode 23. Merge k Sorted Lists 2020.04.14 98
67 Leetcode 729. My Calendar I 2020.04.15 98
66 Leetcode 253. Meeting Rooms II 2020.04.15 98
65 Leetcode 20. Valid Parentheses 2020.04.25 98
64 Leetcode 62. Unique Paths 2020.04.09 99
63 Leetcode 7. Reverse Integer 2020.04.28 100
62 Leetcode 946. Validate Stack Sequences 2020.04.08 101
61 Leetcode 973. K Closest Points to Origin 2020.04.15 101
60 Leetcode 852. Peak Index in a Mountain Array 2020.04.28 101
59 Leetcode 350. Intersection of Two Arrays II 2020.04.28 102
58 Leetcode 443. String Compression 2020.04.25 103
57 Leetcode 38. Count and Say 2020.04.25 103
56 Leetcode 53. Maximum Subarray 2020.04.28 106
55 Leetcode 3. Longest Substring Without Repeating Characters 2020.04.09 107
Board Pagination Prev 1 2 3 4 Next
/ 4