[leetcode][430] Flatten a Multilevel Doubly Linked List

문제 : https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

---

doubly linked list 가 주어진다. 하나의 노드는 next, previous, child 포인터를 가지고 있다.

이를 prev, next만을 가진 linked list로 바꿔라.

child와 next 포인터를 가지고 있다면 child 노드를 next 노드로 잇고 child 노드와 연결된 모든 노드들이 linked list로 만들어졌을 때 그 뒤에 next노드를 다시 이어나간다.

---

dfs로 head 노드에서 child노드가 있다면 child 노드를 잇고 다음 next노드를 잇는 식으로 재귀함수를 만들어서 푼다.

이를 위해 최근 탐색했던 노드 포인터 before와 현재 탐색중인 노드 포인터 now가 필요하다.

탐색중인 now->prev = before, before->next = now. 를 연결한다. 그리고 before 포인터를 now 포인터로 갱신.

만약 now->child가 있다면 이를 먼저 탐색한다. now->child를 nullptr로 세팅.

이후 now->next를 탐색한다.

 

시간복잡도는 모든 노드탐색하므로 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/430.%20Flatten%20a%20Multilevel%20Doubly%20Linked%20List.cpp