面试题：如何展开二维链表结构

题目描述：给定一个有序链表， 其中每个节点也表示有一个有序链表。结点包含两个类型的指针：

1. 指向主链表中下一个结点的指针。
2. 指向此结点的头的链表。
   所有链表都被排序。参见一下实例：

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

实现函数flatten() 该函数用来将链表扁平化成单个链表，扁平化的链表被排序。
例如上面的链表，输出链表为

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

分析与解答

本题的主要思路为使用归并排序中的合并排序，使用归并的方法把这些链表来逐个归并。
具体而言就是可以使用递归算法。归并的合并已经扁平化的链表与当前链表。
首先我们先定义出这个链式的结构

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

我们姑且把最左上角的那个结点称为 root结点。然后我们可以把整个结构看做是 多个列组成。然后就可以把问题看做是两个有序链表的合并了。

Node* Merge(Node* a, Node* b) {
    // 如果有一个链表为空，那么合并后有序链表就是另外一列
    if (a == NULL)
        return b;
    if (b == NULL)
         return a;
    Node* result = NULL;
    // 把 链表a第一个和链表b的第一个进行比较
    // 结果小的down指针指向它的down和另外一个链表合并后的结果
    if (a->value < b->value) {
        result = a;
        result->down =  Merge(a->down, b);
    } else {
        result = b;
        result->down = Merge(a, b->down);
    }
    return result;
}

然后我们进行扩展到多个列就可以得到 flatten()。

Node* flatten(Node* root) {
    if (root == NULL || root->right == NULL)
          return root;
    // 把root->right 看作是已经右边的已经有序的链表，然后通过递归来进行归并
   return Merge(root, flatten(root->right));
}

接下来我们来测试下：

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

using namespace std;

// 进行头插法，把新结点通过 down指针连接到无头结点的链表中，从而形成一列
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;
}

结果为：

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