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

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

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

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

以上示例的說(shuō)明:

給出以下多級(jí)雙向鏈表:

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

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

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

其邏輯以示例輸入為例：

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

從節(jié)點(diǎn) 1 開(kāi)始遍歷，當(dāng)前遍歷鏈表為：1---2---3---4---5---6--NULL

遇到鄰接點(diǎn) 2，其子鏈表為：7---8---9---10--NULL
將子鏈表頭節(jié)點(diǎn) 7 作為參數(shù)傳入 DFS 函數(shù)，當(dāng)前遍歷鏈表為：7---8---9---10---NULL

繼續(xù)遍歷，遇到鄰接點(diǎn) 8，其子鏈表為：11--12--NULL
將子鏈表頭節(jié)點(diǎn) 8 作為參數(shù)傳入 DFS 函數(shù)，當(dāng)前遍歷鏈表為：11--12---NULL

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

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

繼續(xù)遍歷，無(wú)鄰接點(diǎn)，遍歷結(jié)束，返回當(dāng)前鏈表尾節(jié)點(diǎn) 6

遞歸結(jié)束，返回頭節(jié)點(diǎn) 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) {
                //改變當(dāng)前節(jié)點(diǎn)與子節(jié)點(diǎn)的關(guān)系
                Node next = cur.next;//記錄暫存下一個(gè)節(jié)點(diǎn)
                cur.next = cur.child;//當(dāng)前節(jié)點(diǎn)與子鏈表頭節(jié)點(diǎn)連接
                cur.next.prev = cur;
                //傳遞子鏈表頭節(jié)點(diǎn)作為參數(shù)到 dfs
                Node childLast = dfs(cur.child);//childLast獲得返回值為子鏈表的尾節(jié)點(diǎn)
                childLast.next = next;//子鏈表尾節(jié)點(diǎn)與暫存節(jié)點(diǎn)連接
                if (next != null) next.prev = childLast;//暫存節(jié)點(diǎn)不為空就將其prev指向子鏈表尾節(jié)點(diǎn)
                cur.child = null;//子鏈表置空
                cur = childLast;//刷新當(dāng)前節(jié)點(diǎn)，跳過(guò)子鏈表的遍歷
            }
            head = cur;//頭節(jié)點(diǎn)刷新為當(dāng)前節(jié)點(diǎn)
            cur = cur.next;//刷新當(dāng)前節(jié)點(diǎn)
        }
        return head;//返回子鏈表的尾節(jié)點(diǎn)
    }
}

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)注微.信公.眾號(hào)：愛(ài)寫B(tài)ug