讨论/《链表》 - 扁平化多级双向链表/
《链表》 - 扁平化多级双向链表
共 6 个回复
class Solution {
    private Node prevNode = new Node(0);

    public Node flatten(Node head) {
        dfs(head);
        if (head != null) {
            head.prev = null;
        }
        return head;
    }

    private void dfs(Node root) {
        if (root == null) {
            return;
        }
        Node left = root.child;
        Node right = root.next;
        prevNode.next = root;
        root.prev = prevNode;
        prevNode = root;
        dfs(left);
        root.child = null;
        dfs(right);
    }
}
6

image.png

class Solution {
public:
    Node* flatten(Node* head) {
        // 放置游标
        Node *ptr = head;
        while (ptr != NULL) {
            // 若该游标下有子链表
            if (ptr->child != NULL) {
                // 标记母链表游标的下一个位置
                Node *nptr = ptr->next;
                // 放置子链表游标
                Node *Child = ptr->child;
                // 子链表头prev初始化
                Child->prev = ptr;               
                // 母链表游标next指向子链表头
                ptr->next = Child;
                // 子链表扁平化
                Child = flatten(Child);
                // 遍历扁平子链表至子链表尾
                while (Child->next != NULL) {
                    Child = Child->next;
                }
                // 扁平子链表尾next指向母链表游标的下一个位置
                Child->next = nptr;
                // 母链表游标下一个位置的prev指向扁平子链表尾
                if (nptr != NULL) nptr->prev = Child;
                // 删除母链表游标位置的child
                ptr->child = NULL;
                // 推动母链表游标
                ptr = nptr;
            }
            // 若该游标下无子链表
            else {
                // 推动游标
                ptr = ptr->next;
            }
        }
        return head;
    }
};
1
class Solution {
//自己没看答案写的,不知为啥才击败了9.3的人
    public Node flatten(Node head) {
               Stack<Node> stack = new Stack<>();
        Node cur = head;
        Node curNext, childHead, childTail;
        while (cur!=null || !stack.isEmpty()) {
//DFS思想,有子节点就访问子节点一条路走到底
            if (cur.child != null) {
                stack.push(cur);
                cur = cur.child;
                continue;
            }
//已经走到了最下面一层的链表尾部,那就把最下层的链表接到上一层去,上一层会在下一轮循环变成最下一层的链表
            if (cur.next == null && !stack.isEmpty()) {
                childTail = cur;
                cur = stack.pop();
                curNext = cur.next;
                childHead = cur.child;
//上一层只有一个节点的情况和上一层有大于一个节点的情况分别不同操作
                if (cur.next==null){
                    cur.next = childHead;
                    childHead.prev = cur;
                }
                else {
                    cur.next = childHead;
                    childHead.prev = cur;
                    curNext.prev = childTail;
                    childTail.next = curNext;
                }
                
                cur.child = null;
            }
            cur = cur.next;
        }
        return head;
    }
}

c++递归
image.png

class Solution {
public:
    Node* flatten(Node* head) {
        Node *p = head;
        while(p!=nullptr)//遍历
        {
            if(p->child!=nullptr)//如果发现child
            {
                Node *tmp = p->next;//记录断点
                Node *p_cd = flatten(p->child);//先把child给flatten了
                p->next = p_cd;
                p_cd->prev = p;
                p->child = nullptr;//p->next指向flatten后的child
                Node *p2 = p;
                while(p2->next!=nullptr)    p2= p2->next;//p2指针指向flatten的结尾
                p2->next = tmp;//p2连回到之前的断点那
                if(tmp!=nullptr)    tmp->prev = p2;
                p = tmp;//让p走到断点那
            }
            else    p = p->next;
        }
        return head;
    }
};
class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if head is None:
            return head
        first = head
        while first:
            if first.child:
                second = first.child
                while second.next:
                    second = second.next
                second.next = first.next
                if second.next:
                    second.next.prev = second
                first.next = first.child
                if first.next:
                    first.next.prev = first
                first.child = None
                first = head
            else:
                first = first.next
        return head
        

class Solution {
    public Node flatten(Node head) {
        Node first = head;
            while (first != null){
                // 有child时,把child接在当前节点后面
                if (first.child != null) {
                    Node temp = first.next;
                    Node child = first.child;
                    first.child = null;
                    first.next = child;
                    child.prev = first;
                    // 找到child的尾结点
                    while (child.next != null) {
                        child = child.next;
                    }
                    child.next = temp;
                    if (temp != null){
                        temp.prev = child;
                    }
                }
                first = first.next;
            }
            return head;
    }
}