vector<Node<int>*>含义解析：是否为链表集合声明及声明方式

1. 该类型的作用 #

vector<Node<int>*>就是用来存储所有待合并有序链表的容器——其中每个元素Node<int>*都是某一条有序链表的头指针，指向对应链表的第一个节点。

2. 相关类型的声明方式 #

首先需要定义链表节点的结构体，通常有两种写法：

模板版本（支持任意数据类型）

template<typename T>
struct Node {
    T val;
    Node<T>* next;
    Node(T x) : val(x), next(nullptr) {}
};

针对int类型的非模板版本

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

之后，声明vector<Node<int>*>类型的变量和普通vector的声明方式一致：

vector<Node<int>*> listArray;

3. 如何向容器中添加待合并链表 #

举个实际例子，假设我们有3条有序链表：

• 链表1: 1 -> 4 -> 5
• 链表2: 1 -> 3 -> 4
• 链表3: 2 -> 6

可以这样创建并将它们加入容器：

// 创建链表1
Node<int>* l1 = new Node<int>(1);
l1->next = new Node<int>(4);
l1->next->next = new Node<int>(5);

// 创建链表2
Node<int>* l2 = new Node<int>(1);
l2->next = new Node<int>(3);
l2->next->next = new Node<int>(4);

// 创建链表3
Node<int>* l3 = new Node<int>(2);
l3->next = new Node<int>(6);

// 将三条链表的头指针加入vector
listArray.push_back(l1);
listArray.push_back(l2);
listArray.push_back(l3);

完成后就可以调用mergeKLists(listArray)来合并这些有序链表了。

内容的提问来源于stack exchange，提问作者cosmoabhi