【leetcode】【剑指offer Ⅱ】028. 展平多级双向链表

问题描述：

• 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。
  • 将多级双向链表扁平化，使其所有节点都出现在单级双链表中。
• 例子如下：

  // 输入：[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
  // 解释如下：
  // 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]
  // 解释如下：
  // 1---2---3---7---8---11---12---9---10---4---5---6--NULL
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11

核心思路：

• 该题的递归解法较为直观。
• 在当前节点 head，以如下步骤进行处理：
  1. 递归处理 head->next，将递归返回的节点保存为 tmp。【保存 head->next，准备断开链】
  2. 递归处理 head->child，将 head->next 置为递归返回的结果，此时 head->next = head->child，因为是双向链表，所以需要反过来再连接，即 head->next->prev = head。【此时已经处理好 head 和 head->child 的关系，后续就是处理 head 和 tmp 的连接关系】
  3. 接着保存当前 head 为 ret 以便最后返回，即 ret = head。
  4. head 此时连接着 head->child，则将 head 向后移动直到走尽，走尽后将尾部与 tmp 连接。
  5. 最后将 ret 作为链表头返回。
• 上述的步骤主要就是完成了以下任务：连接 head 和 head->child、走尽 head、连接 head 和原来的 head->next。

代码实现：

• 递归解法代码实现如下：

  class Solution
  {
  public:
      Node* flatten(Node* head)
      {
          if(!head) return head;
          // 递归处理 head->next
          Node* tmp = flatten(head->next);
          // 递归处理 head->child
          head->next = flatten(head->child);
          head->child = nullptr;
          if(head->next)
              head->next->prev = head;
          // 保存当前 head 为 ret
          Node* ret = head;
          // 走尽 head，并连接 head 和 tmp
          while(head->next) head = head->next;
          head->next = tmp;
          if(tmp) tmp->prev = head;
          return ret;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22