美文网首页
面试题:如何展开二维链表结构

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

作者: 小pb | 来源:发表于2019-12-05 18:37 被阅读0次

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

  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->

相关文章

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

    题目描述:给定一个有序链表, 其中每个节点也表示有一个有序链表。结点包含两个类型的指针: 指向主链表中下一个结点的...

  • 《剑指Offer》-Exercise(C语言)

    面试题4:二维数组中的查找 面试题6:从尾到头打印链表 单链表从尾到头打印(用栈或递归) 单链表结构 面试题7:重...

  • 剑指offer目录

    目录 面试题3 在二维数组中查找 面试题15 链表中倒数第K个数 面试题16 反转链表 面试题44 扑克牌的顺子

  • 算法面经--单链表的操作

    单链表操作(附:新浪百度腾讯面试题) 一、单链表介绍 1.1 单链表在内存中的样子 (物理结构) 1.2 逻辑结构...

  • 链表反转

    概述 链表反转是非常经典的面试题,要实现此功能,需先实现链表的数据结构。 链表类 获得单向链表方法 输出单向链表方...

  • NO.3 Redis 数据结构之hash 字典

    hash 和java的hashmap很像,无序,内部实现结构数组+链表二维结构。第一维位置碰撞时,将会使用链表将碰...

  • 学习JavaScript数据结构与算法(第2版)

    二维和多维数组 栈数据结构 队列数据结构(排队) 链表数据结构 双向链表 集合 字典和散列表 散列表 树 二叉树 ...

  • 大厂面试系列(七):数据结构与算法等

    数据结构和算法 链表 链表,常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分,这个一...

  • 剑指offer之(链表和栈)

    题目列表链表面试题06. 从尾到头打印链表面试题18. 删除链表的节点面试题22. 链表中倒数第k个节点面试题24...

  • 数据结构之 swift 实现链表反转

    链表反转很熟悉的面试题,关于链表的基础知识就不再累赘了,如何swift实现链表的反转。 传入链表的头结点 返回一个...

网友评论

      本文标题:面试题:如何展开二维链表结构

      本文链接:https://www.haomeiwen.com/subject/iakjgctx.html