💯 Daily LeetCode Challenge Day_10 - Flatten a Multilevel Doubly Linked List

Flatten a Multilevel Doubly Linked List - LeetCode

---

문제

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.

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:

Constraints:

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

---

재귀 함수를 써야할 것 같았다.

LinkedList 를 traverse 하면서 child를 발견하면 child 도 traverse 하는 느낌

문제는 child의 linkedList 의 head 와 tail 을 parent 의 node 에 연결해야 한다는 것이다.

parent를 traverse 하다 childnode 를 발견하면 parent.next = parent.child, parent.child = nil 같이 head 부분을 연결 해 준다.

마찬가지로 tail 를 찾아주어 current.next.prev = tail, tail.next = current.next로 tail 부분을 연결해 준다.

마지막으로 child를 nil로 없애준다.

/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var prev: Node?
 *     public var next: Node?
 *     public var child: Node?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.prev = nil
 *         self.next = nil
 *         self.child  = nil
 *     }
 * }
 */

class Solution {   
    func flatten(_ head: Node?) -> Node? {
        let answer = head
        findChild(answer)
        return answer
    }
    func findChild(_ head : Node?){
        guard head != nil else {return}
        var current = head
        //finding node that has child
        while current?.child == nil , current?.next != nil {
            current = current?.next
        }
        //찾은 node를 재귀에 넣음
        findChild(current?.child)
        
        //child linkedlist 의 tail 를 구함
        var lastChild = current?.child
        while lastChild?.next != nil {
            lastChild = lastChild?.next
        }
        /* tail 연결 */
        //child linkedlist 의 tail 을 current.next에 붙임
        lastChild?.next = current?.next
        //current의 다음 것의 이전 node 를 tail 에 붇임
        current?.next?.prev = lastChild
        /* head 연결 */
        current?.next = current?.child
        current?.child?.prev = current
        //child 없앰
        current?.child = nil
    
    }
}