[LeetCode] 430. Flatten a Multilevel Doubly Linked List

grandyang commented 5 years ago

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.

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:

We should return the following flattened doubly linked list:

这道题给了一个多层的双向链表，让我们压平成为一层的双向链表，题目中给了形象的图例，不难理解题意。根据题目中给的例子，我们可以看出如果某个结点有下一层双向链表，那么下一层双向链表中的结点就要先加入进去，如果下一层链表中某个结点还有下一层，那么还是优先加入下一层的结点，整个加入的机制是DFS的，就是有岔路先走岔路，走到没路了后再返回，这就是深度优先遍历的机制。好，那么既然是DFS，肯定优先考虑递归啦。方法有了，再来看具体怎么递归。由于给定的多层链表本身就是双向的，所以我们只需要把下一层的结点移到第一层即可，那么没有子结点的结点就保持原状，不作处理。只有对于那些有子结点的，我们需要做一些处理，由于子结点链接的双向链表要加到后面，所以当前结点之后要断开，再断开之前，我们用变量 next 指向下一个链表，然后对子结点调用递归函数，我们 suppose 返回的结点已经压平了，那么就只有一层，就相当于要把这一层的结点加到断开的地方，所以需要知道这层的最后一个结点的位置，我们用一个变量 last，来遍历到压平的这一层的末结点。现在就可以开始链接了，首先把子结点链到 cur 的 next，然后把反向指针 prev 也链上。此时 cur 的子结点 child 可以清空，然后压平的这一层的末节点 last 链上之前保存的 next 结点，如果 next 非空，那么链上反向结点 prev。这些操作完成后，我们就已经将压平的这一层完整的加入了之前层断开的地方，继续在之前层往下遍历即可，参见代码如下：

解法一：

class Solution {
public:
    Node* flatten(Node* head) {
        Node *cur = head;
        while (cur) {
            if (cur->child) {
                Node *next = cur->next;
                cur->child = flatten(cur->child);
                Node *last = cur->child;
                while (last->next) last = last->next;
                cur->next = cur->child;
                cur->next->prev = cur;
                cur->child = NULL;
                last->next = next;
                if (next) next->prev = last;
            }
            cur = cur->next;
        }
        return head;
    }
};

我们其实也可以不用递归，链表的题不像树的题，对于树的题使用递归可以很简洁，而链表递归和迭代可能差的并不多。如果你仔细对比两种方法的代码，你会发现迭代的写法刚好比递归的写法少了调用递归的那一行，给人一种完全没有必要使用递归的感觉，其实两种解法的操作顺序不同的，递归写法是从最底层开始操作，先把最底层加入倒数第二层，再把混合后的层加入倒数第三层，依此类推，直到都融合到第一层为止。而迭代的写法却是反过来的，先把第二层加入第一层，此时第二层底下可能还有很多层，不必理会，之后等遍历到的时候，再一层一层的加入第一层中，不管哪种方法，最终都可以压平，参见代码如下：

解法二：

class Solution {
public:
    Node* flatten(Node* head) {
        Node *cur = head;
        while (cur) {
            if (cur->child) {
                Node *next = cur->next;
                Node *last = cur->child;
                while (last->next) last = last->next;
                cur->next = cur->child;
                cur->next->prev = cur;
                cur->child = NULL;
                last->next = next;
                if (next) next->prev = last;    
            }
            cur = cur->next;
        }
        return head;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/430

类似题目：

Flatten Binary Tree to Linked List

参考资料：

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/discuss/137649/Simple-Java-Solution

https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/discuss/152066/c%2B%2B-about-10-lines-solution

LeetCode All in One 题目讲解汇总(持续更新中...)

pengxu7 commented 5 years ago

标题和内容是两道不同的题

grandyang commented 5 years ago

标题和内容是两道不同的题

已修改，多谢指出～若还有不同的，请继续告诉博主哈～

liabixiaoxin commented 4 years ago

两个解答都是一样的非递归

ZHAOYI23333 commented 4 years ago

递归解法里边 cur = cur->next; 会把上次递归访问过的（已经flatten了的）child list里的node重新过一遍，这个可以优化一下，如果child存在就直接在if loop结束时把cur赋值给*last的next，否则就cur = cur->next。

lld2006 commented 4 years ago

可以用递归返回找到的最后一个node，这样就不用再访问一遍寻找最后一个node了, 递归写法和解法二一样


class Solution {
public:
    Node* flatten(Node* head) {helper(head); return head;}
    Node* helper(Node* head){
      Node* node = head, *nodeNext = nullptr, *lastNode=nullptr;
      while(node){
        nodeNext = node->next;
        lastNode = node;
        if(node->child){
          Node* childLast = helper(node->child);   
          Node* child = node->child;
          node->next = child;
          child->prev = node;
          childLast->next=nodeNext;
          if(nodeNext) nodeNext->prev = childLast;
          node->child = nullptr;
          lastNode = childLast;
        }
        node = nodeNext;
      }
      return lastNode; 
    }
};

LenaShengzhen commented 3 years ago

Node* flatten(Node* head) {
        Node* pre = NULL;
        recursive(head, pre);
        return head;
    }

void recursive(Node* head, Node*& pre){
   if(!head) return;
   Node* child = head->child;
   Node* next = head->next; 
    if(pre){  
     pre->next = head;    
     head->prev = pre;
     pre->child = NULL;
    }
   pre = head;
   recursive(child, pre);
   recursive(next, pre); 
}

Like preorder-traverse of binary tree!
和先序遍历树的模板比起来，唯一的区别就是要记录下head的子节点和next节点，因为前面在设置next prev指针的时候会改变head->next的值，如果后面还像树的遍历一样写成recursive(head->next)就会出问题，所以提前用next，pre记录下head的next prev指针的值。就这唯一一个区别点。兄dei，你们真的是不是搞得太复杂了！

zh-12345 commented 3 years ago

Node* flatten(Node* head) {
        Node* pre = NULL;
        recursive(head, pre);
        return head;
    }

void recursive(Node* head, Node*& pre){
   if(!head) return;
   Node* child = head->child;
   Node* next = head->next; 
    if(pre){  
     pre->next = head;    
     head->prev = pre;
     pre->child = NULL;
    }
   pre = head;
   recursive(child, pre);
   recursive(next, pre); 
}
Like preorder-traverse of binary tree! 和先序遍历树的模板比起来，唯一的区别就是要记录下head的子节点和next节点，因为前面在设置next prev指针的时候会改变head->next的值，如果后面还像树的遍历一样写成recursive(head->next)就会出问题，所以提前用next，pre记录下head的next prev指针的值。就这唯一一个区别点。兄dei，你们真的是不是搞得太复杂了！

这个方法好像跳不出递归？？？next 回到最上层的时候，跳不出去。

LenaShengzhen commented 3 years ago

Node* flatten(Node* head) {
        Node* pre = NULL;
        recursive(head, pre);
        return head;
    }

void recursive(Node* head, Node*& pre){
   if(!head) return;
   Node* child = head->child;
   Node* next = head->next; 
    if(pre){  
     pre->next = head;    
     head->prev = pre;
     pre->child = NULL;
    }
   pre = head;
   recursive(child, pre);
   recursive(next, pre); 
}
Like preorder-traverse of binary tree! 和先序遍历树的模板比起来，唯一的区别就是要记录下head的子节点和next节点，因为前面在设置next prev指针的时候会改变head->next的值，如果后面还像树的遍历一样写成recursive(head->next)就会出问题，所以提前用next，pre记录下head的next prev指针的值。就这唯一一个区别点。兄dei，你们真的是不是搞得太复杂了！
这个方法好像跳不出递归？？？next 回到最上层的时候，跳不出去。

AC后，我才发的贴。

zh-12345 commented 3 years ago

Node* flatten(Node* head) {
        Node* pre = NULL;
        recursive(head, pre);
        return head;
    }

void recursive(Node* head, Node*& pre){
   if(!head) return;
   Node* child = head->child;
   Node* next = head->next; 
    if(pre){  
     pre->next = head;    
     head->prev = pre;
     pre->child = NULL;
    }
   pre = head;
   recursive(child, pre);
   recursive(next, pre); 
}
Like preorder-traverse of binary tree! 和先序遍历树的模板比起来，唯一的区别就是要记录下head的子节点和next节点，因为前面在设置next prev指针的时候会改变head->next的值，如果后面还像树的遍历一样写成recursive(head->next)就会出问题，所以提前用next，pre记录下head的next prev指针的值。就这唯一一个区别点。兄dei，你们真的是不是搞得太复杂了！
这个方法好像跳不出递归？？？next 回到最上层的时候，跳不出去。
AC后，我才发的贴。

emmmm, 不好意思，我是指我按照您提供的思路写的程序跳不出递归，还没找到问题，不过您的思路的确是相当清晰，是我还没理解到位，抱歉。

grandyang / leetcode

[LeetCode] 430. Flatten a Multilevel Doubly Linked List #430