Leetcode - Flatten a Multilevel Doubly Linked List

https://leetcode.com/problems/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.

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:

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Prev *Node
 *     Next *Node
 *     Child *Node
 * }
 */

func flatten(root *Node) *Node {
    if root == nil {
        return nil
    }
    stack := []*Node{}
    node := root
    var prev *Node
    for node != nil || len(stack) != 0 {
        for node != nil && node.Child == nil {
            prev = node
            node = node.Next
        }
        if node != nil && node.Child != nil {
            if node.Next != nil {
                stack = append(stack, node.Next)
            }               
            node.Next = node.Child
            node.Child.Prev = node
            node.Child = nil
            node = node.Next
            continue
        }
        if node == nil && len(stack) != 0 {
            node = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            prev.Next = node
            node.Prev = prev
            prev = node
            node = node.Next
        }
        
    }
    //Print(root)
    return root
}

func Print(root *Node) {
    node := root
    for node != nil {
        fmt.Println("===========")
        fmt.Println("node.Val: ", node.Val)
        fmt.Println("node.Prev: ", node.Prev)
        fmt.Println("node.Next: ", node.Next)
        fmt.Println("node.Child: ", node.Child)
        node = node.Next
    }
}

• 相关文章
• 全局相关文章