Linked List | Flatten a Multilevel Doubly Linked List

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.

양쪽으로 포인터를 가지고있는 Doubly Linked List에 child가 있는 형태에서, Flatten 하라는 문제이다. getTail이라는 함수를 구현해서, Child가 있는 노드는, 그다음 노드사이에 child 노드부터 child의 tail 까지 연결해주는 형식으로 구현했다. getTail이라는 함수가 불려지고, 또 기존 포인터는 앞쪽부터 하나씩 가기때문에 2N번까지 노드를 방문할 수 있다. 

 

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

class Solution {
    public Node flatten(Node head) {
        if(head == null) return head;
        Node curr = head;
        while(curr != null){
            if(curr.child == null){
                curr = curr.next;
            } else {
                Node childTail = getTail(curr.child);
                childTail.next = curr.next;
                if(curr.next != null){
                    curr.next.prev = childTail;
                }
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child = null;
            }
        }
        return head;
    }
    
    private Node getTail(Node node){
        while(node != null && node.next != null){
            node = node.next;
        }
        return node;
    }
}

* Time Complexity: O(N)

* Space Complexity: O(1)

 

 

속도면에서 100%에 해당하는 최상위 속도를 보였다!

 

피카츄들! 일렬로 정렬하자! Flatten Method 안으로 드루와

 

 

Reference

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

Flatten a Multilevel Doubly Linked List - LeetCode