Written by Lee Jongseo
on May 06, 2021

Alogrithm[0]:⭐⭐

Q. Leetcode: 430. Flatten a Multilevel Doubly Linked List

(Doubly) Linked List and Stack

Linked List는 head 노드를 통해서 List의 데이터에 접근한다.
Doubly Linked List는 prev 를 통해서 이전 노드에도 접근할 수 있다.
Stack은 LIFO 구조를 가지고 있다. 가장 최신의 값부터 처리할 수 있다.
어떤 리스트의 데이터를 스택에 전부 push하고 전부 pop을 하여 리스트를 만들면 original 리스트의 역순 리스트가 만들어진다.

문제 이해하기

위 leetcode 문제에 나온 Doubly Linkde List의 Node는 child 라는 요소를 하나 더 가지고 있다.

class Node:
    def __init__(self, val, prev, `next`, `child`):
        self.val = val
        self.prev = prev
        self.`next` = `next`
        self.`child` = `child`

prev와 next는 동일한 레벨의 노드와 연결되어 있고 child는 한 단계 낮은 레벨의 리스트의 노드와 연결되어 있다.

주어진 리스트는 다음과 같다.

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

각각의 레벨을 serialization하면 다음과 같다.

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

레벨과 connection 되어 있지 않은 부분에 null을 추가하여 하나의 리스트로 serialization한다.

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

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

여기서 문제는 head가 주어졌을 때, 리스트에 존재하는 레벨을 없애고 flatten하라는 것.

Node 3의 child가 Node 7을 포인팅하고 있고 Node 7은 7->8->9->10의 head이다.그리고
Node 8의 child는 Node 11을 포인팅하고 있고 Node 11은 11->12의 head다.

따라서 이를 flatten하면 아래와 같이 된다.

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

스택으로 문제 해결하기

head를 가진 스택으로 초기화한다.
스택에서 노드를 pop한다.
노드가 next를 가지고 있으면 노드의 next를 push한다.
노드가 child를 가지고 있으면 push하고 노드의 child에 None을 할당한다.
2번 반복

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

root 노드를 생성한다 – 0

스택을 생성한다. – []
head을 스택에 push한다. – [1]

스택을 pop한다. – 1, []
노드에 next가 있다면 push한다. – [2]
노드에 child가 있다면 push한다. – [2]
0 -> 1

스택을 pop한다. – 2, []
노드에 next가 있다면 push한다. – [3]
노드에 child가 있다면 push한다. – [3]
0 -> 1 -> 2

스택을 pop한다. – 3, []
노드에 next가 있다면 push한다. – [4]
노드에 child가 있다면 push한다. – [4, 7]
0 -> 1 -> 2 -> 3

스택을 pop한다. – 7, [4]
노드에 next가 있다면 push한다. – [4, 8]
노드에 child가 있다면 push한다. – [4, 8]
0 -> 1 -> 2 -> 3 -> 7

스택을 pop한다. – 8, [4]
노드에 next가 있다면 push한다. – [4, 9]
노드에 child가 있다면 push한다. – [4, 9, 11]
0 -> 1 -> 2 -> 3 -> 7 -> 8

스택을 pop한다. – 11, [4, 9]
노드에 next가 있다면 push한다. – [4, 9, 12] 노드에 child가 있다면 push한다. – [4, 9, 12]
0 -> 1 -> 2 -> 3 -> 7 -> 8 -> 11

이런 식으로 진행한다.

스택은 우선적으로 처리해야 할 값들을 먼저 처리하고 나중에 처리해야 할 값은 스택에 남게 된다.

최종적으로 우선적으로 처리해야 할 값을 처리하고 나면 되돌아와 이전 값을 처리한다.

Code

Leetcode의 문제는 Doubly Linked List지만 그냥 Linked List여도 될 것 같다. 그냥 Linked List라고 가정하고 코드를 작성한다.

class Solution:
    def flatten(self, head):
        if not head:
            return
        stack = [head] # init stack
        prev = Node(0)
        while stack:
            node = stack.pop()
            prev.next = node
            prev = node
            # node.next부터 담고 그 다음 node.child를 담는다.
            if node.next:
                stack.append(node.next)
            if node.child:
                stack.append(node.child)
                note.child = None # child를 없앤다.
        return head

👈 👉 Top