国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 430:扁平化多級雙向鏈表 Flatten a Multilevel Doubly

sugarmo / 2010人閱讀

摘要:您將獲得一個雙向鏈表,除了下一個和前一個指針之外,它還有一個子指針,可能指向多帶帶的雙向鏈表。扁平化列表,使所有結(jié)點出現(xiàn)在單級雙鏈表中。

您將獲得一個雙向鏈表,除了下一個和前一個指針之外,它還有一個子指針,可能指向多帶帶的雙向鏈表。這些子列表可能有一個或多個自己的子項,依此類推,生成多級數(shù)據(jù)結(jié)構(gòu),如下面的示例所示。

扁平化列表,使所有結(jié)點出現(xiàn)在單級雙鏈表中。您將獲得列表第一級的頭部。

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.

示例:

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

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

以上示例的說明:

給出以下多級雙向鏈表:

我們應(yīng)該返回如下所示的扁平雙向鏈表:

解題思路:

這道題是典型的 DFS(深度優(yōu)先搜索)型例題,并且給出了圖解,只要了解過 DFS 的應(yīng)該立即就能想到思路。

針對這道題簡單說下:深度優(yōu)先搜索 就像一棵樹(二叉樹)的前序遍歷,從某個頂點(鏈表頭節(jié)點)出發(fā),自頂向下遍歷,然后遇到頂點的未被訪問的鄰接點(子節(jié)點 Child),繼續(xù)進行深度優(yōu)先遍歷,重復(fù)上述過程(遞歸),直到所有頂點都被訪問為止。

其邏輯以示例輸入為例:

 1---2---3---4---5---6--NULL
       |
        7---8---9---10--NULL
              |
             11---12---NULL
從節(jié)點 1 開始遍歷,當前遍歷鏈表為:1---2---3---4---5---6--NULL

遇到鄰接點 2,其子鏈表為:7---8---9---10--NULL
將子鏈表頭節(jié)點 7 作為參數(shù)傳入 DFS 函數(shù),當前遍歷鏈表為:7---8---9---10---NULL

繼續(xù)遍歷,遇到鄰接點 8,其子鏈表為:11--12--NULL
將子鏈表頭節(jié)點 8 作為參數(shù)傳入 DFS 函數(shù),當前遍歷鏈表為:11--12---NULL

繼續(xù)遍歷,無鄰接點,遍歷結(jié)束,返回當前鏈表尾節(jié)點 12
改變鄰接點 8 與子鏈表頭節(jié)點 11 關(guān)系:7---8---11---12
連接返回值 尾節(jié)點 12 和鄰接點的下一個節(jié)點 9: 7---8---11---12---9---10---NULL

繼續(xù)遍歷,無鄰接點,遍歷結(jié)束,返回當前鏈表尾節(jié)點 10
改變鄰接點 2 與 子鏈表頭節(jié)點 7 關(guān)系:1---2---7---8---11---12---9---10--NULL
連接返回值 尾節(jié)點 10 和鄰接點的下一個節(jié)點 3: 1---2---7---8---11---12---9---10---3---4---5---6--NULL

繼續(xù)遍歷,無鄰接點,遍歷結(jié)束,返回當前鏈表尾節(jié)點 6

遞歸結(jié)束,返回頭節(jié)點 1,鏈表為: 1---2---7---8---11---12---9---10---3---4---5---6--NULL

Java:

class Solution {
    public Node flatten(Node head) {
        dfs(head);
        return head;
    }
    //深度優(yōu)先搜索函數(shù)
    private Node dfs(Node head) {
        Node cur = head;
        while (cur != null) {
            if (cur.child != null) {
                //改變當前節(jié)點與子節(jié)點的關(guān)系
                Node next = cur.next;//記錄暫存下一個節(jié)點
                cur.next = cur.child;//當前節(jié)點與子鏈表頭節(jié)點連接
                cur.next.prev = cur;
                //傳遞子鏈表頭節(jié)點作為參數(shù)到 dfs
                Node childLast = dfs(cur.child);//childLast獲得返回值為子鏈表的尾節(jié)點
                childLast.next = next;//子鏈表尾節(jié)點與暫存節(jié)點連接
                if (next != null) next.prev = childLast;//暫存節(jié)點不為空就將其prev指向子鏈表尾節(jié)點
                cur.child = null;//子鏈表置空
                cur = childLast;//刷新當前節(jié)點,跳過子鏈表的遍歷
            }
            head = cur;//頭節(jié)點刷新為當前節(jié)點
            cur = cur.next;//刷新當前節(jié)點
        }
        return head;//返回子鏈表的尾節(jié)點
    }
}

Python3:

class Solution:
    def flatten(self, head: "Node") -> "Node":
        self.dfs(head)
        return head

    def dfs(self, head):
        cur = head
        while cur:
            if cur.child:
                next = cur.next
                cur.next = cur.child
                cur.next.prev = cur
                childLast = self.dfs(cur.child)
                childLast.next = next
                if next: next.prev = childLast
                cur.child = None
            head = cur
            cur = cur.next
        return head

歡迎關(guān)注微.信公.眾號:愛寫B(tài)ug

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/75586.html

相關(guān)文章

  • LeetCode 430平化多級雙向鏈表 Flatten a Multilevel Doubly

    摘要:您將獲得一個雙向鏈表,除了下一個和前一個指針之外,它還有一個子指針,可能指向單獨的雙向鏈表。扁平化列表,使所有結(jié)點出現(xiàn)在單級雙鏈表中。 您將獲得一個雙向鏈表,除了下一個和前一個指針之外,它還有一個子指針,可能指向單獨的雙向鏈表。這些子列表可能有一個或多個自己的子項,依此類推,生成多級數(shù)據(jù)結(jié)構(gòu),如下面的示例所示。 扁平化列表,使所有結(jié)點出現(xiàn)在單級雙鏈表中。您將獲得列表第一級的頭部。 Yo...

    dabai 評論0 收藏0
  • [LeetCode] 430. Flatten a Multilevel Doubly Linked

    摘要: Problem 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...

    curried 評論0 收藏0
  • leetcode430. Flatten a Multilevel Doubly Linked Li

    摘要:步驟如下代碼如下思路二循環(huán)上面的思路同樣可以通過循環(huán)的方式來解決。基本步驟如下代碼如下思路減少遍歷次數(shù)之前的兩種思路,都會出現(xiàn)大量的重復(fù)遍歷,重復(fù)遍歷和葉子節(jié)點的深度成正相關(guān),可以想方法將重復(fù)遍歷的次數(shù)減少。 題目要求 You are given a doubly linked list which in addition to the next and previous pointe...

    gxyz 評論0 收藏0
  • LeetCode707:設(shè)計鏈表 Design Linked List

    摘要:愛寫設(shè)計鏈表的實現(xiàn)。單鏈表中的節(jié)點應(yīng)該具有兩個屬性和。插入后,新節(jié)點將成為鏈表的第一個節(jié)點。將值為的節(jié)點追加到鏈表的最后一個元素。如果等于鏈表的長度,則該節(jié)點將附加到鏈表的末尾。如果索引有效,則刪除鏈表中的第個節(jié)點。操作次數(shù)將在之內(nèi)。 愛寫bug (ID:iCodeBugs) 設(shè)計鏈表的實現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點應(yīng)該具有兩個屬性:val 和 next。val 是...

    iliyaku 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<