个人中心
gpt4 book ai didi

430. Flatten a Multilevel Doubly Linked List 扁平化多级双向链表

转载 作者：大佬之路 更新时间：2024-01-31 14:17:15 25 4
gpt4 key购买 nike

题目地址：https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/description/

题目描述：

Youare 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:

Input:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

Explanation for the above example:

Given the following multilevel doubly linked list:

 

Weshould return the following flattened doubly linked list:

 

题目大意

给出的是一个带有子节点的双向链表。要求把这个带有子节点的双向链表转化为一个不带子节点的双向链表，其规则是把子节点所有的节点都插入到该节点的后面。

解题方法

看到把子节点插入到后面，就想到了我们应该使用的是DFS，这种搜索方式会让我们提前使用更深层次的节点，当更深层次的搜索结束之后再往上层返回。

现在的思路就是每次遇到child节点，就把这个节点作为当前node的next节点；并且要遍历child节点后面的所有节点，找到child链表最后面的节点，作为要插入的一整段链表最后的节点，即原node.next节点prev节点。

做法需要新定义一个函数，这个函数对每个child链表进行遍历，把整段的child链表插入到原链表中。

思路总结就是：DFS负责查找，新定义的函数负责插入。

代码如下：

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""
class Solution(object):
    def flatten(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head: return None
        node = head
        while node:
            node_next = node.next
            if node.child:
                flattened = self.flatten(node.child)
                node.child = None
                nextNode = self.appendToList(node, flattened)
                node = nextNode
            else:
                node = node.next
        return head
    
    def appendToList(self, node, listToAppendHead):
        next_node = node.next
        node.next = listToAppendHead
        listToAppendHead.prev = node
        while node.next:
            node = node.next
        node.next = next_node
        if next_node:
            next_node.prev = node
        return next_node

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

参考资料：https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/discuss/162164/In-place-merge-using-DFS

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

25 4 0
文章推荐： 433. Minimum Genetic Mutation 最小基因变化
文章推荐： 735. Asteroid Collision 行星碰撞
文章推荐： 738. Monotone Increasing Digits 单调递增的数字
文章推荐： 712. Minimum ASCII Delete Sum for Two Strings 两个字符串的最小ASCII删除和
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com