題目描述：給定一個(gè)有序鏈表， 其中每個(gè)節(jié)點(diǎn)也表示有一個(gè)有序鏈表。結(jié)點(diǎn)包含兩個(gè)類型的指針：

1. 指向主鏈表中下一個(gè)結(jié)點(diǎn)的指針。
2. 指向此結(jié)點(diǎn)的頭的鏈表。
   所有鏈表都被排序。參見(jiàn)一下實(shí)例：

  3 -> 11 -> 15 -> 30
  |     |     |     |
  6    21    22    39
  |           |     |
  8          50    40
  |                 |
  31               55

實(shí)現(xiàn)函數(shù)flatten() 該函數(shù)用來(lái)將鏈表扁平化成單個(gè)鏈表，扁平化的鏈表被排序。
例如上面的鏈表，輸出鏈表為

3 -> 6 -> 8 -> 11 -> 15 -> 21 -> 22 ->
30 -> 31 -> 39 -> 40 -> 45 -> 50

分析與解答

本題的主要思路為使用歸并排序中的合并排序，使用歸并的方法把這些鏈表來(lái)逐個(gè)歸并。
具體而言就是可以使用遞歸算法。歸并的合并已經(jīng)扁平化的鏈表與當(dāng)前鏈表。
首先我們先定義出這個(gè)鏈?zhǔn)降慕Y(jié)構(gòu)

typedef struct Node {
    int value;
    Node* right;
    Node* down;
}Node;

我們姑且把最左上角的那個(gè)結(jié)點(diǎn)稱為 root結(jié)點(diǎn)。然后我們可以把整個(gè)結(jié)構(gòu)看做是 多個(gè)列組成。然后就可以把問(wèn)題看做是兩個(gè)有序鏈表的合并了。

Node* Merge(Node* a, Node* b) {
    // 如果有一個(gè)鏈表為空，那么合并后有序鏈表就是另外一列
    if (a == NULL)
        return b;
    if (b == NULL)
         return a;
    Node* result = NULL;
    // 把 鏈表a第一個(gè)和鏈表b的第一個(gè)進(jìn)行比較
    // 結(jié)果小的down指針指向它的down和另外一個(gè)鏈表合并后的結(jié)果
    if (a->value < b->value) {
        result = a;
        result->down =  Merge(a->down, b);
    } else {
        result = b;
        result->down = Merge(a, b->down);
    }
    return result;
}

然后我們進(jìn)行擴(kuò)展到多個(gè)列就可以得到 flatten()。

Node* flatten(Node* root) {
    if (root == NULL || root->right == NULL)
          return root;
    // 把root->right 看作是已經(jīng)右邊的已經(jīng)有序的鏈表，然后通過(guò)遞歸來(lái)進(jìn)行歸并
   return Merge(root, flatten(root->right));
}

接下來(lái)我們來(lái)測(cè)試下：

#include <iostream>
#include <stdlib.h>

using namespace std;

// 進(jìn)行頭插法，把新結(jié)點(diǎn)通過(guò) down指針連接到無(wú)頭結(jié)點(diǎn)的鏈表中，從而形成一列
void Insert(Node **head_ref, int new_data) {                                             
  LinkList new_node = (LinkList)malloc(sizeof(Node));                                    
  new_node->right = NULL;                                                                
  new_node->value = new_data;    
  new_node->down = (*head_ref);    
  (*head_ref) = new_node;    
}  

int main() {

  Node* root = NULL;

  Insert(&root, 31);    
  Insert(&root, 8);    
  Insert(&root, 6);    
  Insert(&root, 3);    
    
  Insert(&(root->right), 21);    
  Insert(&(root->right), 11);    
    
  Insert(&(root->right->right), 50);    
  Insert(&(root->right->right), 22);    
  Insert(&(root->right->right), 15);    
    
  Insert(&(root->right->right->right), 55);    
  Insert(&(root->right->right->right), 40);                                              
  Insert(&(root->right->right->right), 39);                                              
  Insert(&(root->right->right->right), 30); 

  root = FlattenList(root);

  Node* tmp = root;

  while (tmp != NULL) {
    cout << tmp->value << "-> ";
    tmp = tmp->down;
  }

  FreeList(root);
  return 0;
}

結(jié)果為：

[root@VM_16_3_centos data_struct]$ ./list/flatten_list
3-> 6-> 8-> 11-> 15-> 21-> 22-> 30-> 31-> 39-> 40-> 50-> 55->