leetCode-430:Flatten a Multilevel Doubly Linked List

问题描述

给定一个链表，链表可能存在多层，要求将链表偏平化。题目链接：点我

样例输入输出

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

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

解释：输入的链表如下

输出的链表如下

输入：head = []

输出：[]

问题解法

使用递归将子链表偏平化后再进行连接，为了避免重复遍历节点，可以在扁平化的过程中将子链表最后节点直接对接到父链表的下个节点上。代码如下

/*
// 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) {
        flatten(head, null);
        return head;
    }

    public void flatten(Node head, Node next) {
        if (head == null) {
            return;
        }
        
        Node current = head;
        while (current.next != null && current.child == null) {
            current = current.next;
        }
        
        if (current.child == null) {
            current.next = next;
            if (next != null) {
                next.prev = current;
            }
        } else {
            Node nextStep = current.next;
            Node childNode = current.child;
            flatten(childNode, nextStep == null ? next : nextStep);
            current.next = childNode;
            childNode.prev = current;
            current.child = null;
            flatten(nextStep, next);
        }
    }
}