I was solving a question on merging k sorted linked lists and I came across this vector<Node<int>*>:

Node<int>* mergeKLists(vector<Node<int>*> &listArray);

I want to know if it is a declaration of all the linked lists, if it is how it has been declared?

CodePudding user response：

what is the meaning of vector<Node*>

It's a vector of pointers to Nodes, where each Node pointed to is the first node of a linked list. The size of the vector would be K, corresponding to K linked lists. Each Node has one data member, an integer.

Node<int>* mergeKLists(vector<Node<int>*> &listArray);

The function merges the K linked lists and returns a single list. I don't know why the name listArray was chosen since the parameter is a vector.

Based on the comment below, these are single linked lists.

CodePudding user response：

• Node<int> is a linked list node.
• Node<int>* is a pointer to a linked list node.
• std::vector<Node<int>*> is a vector of pointers to a linked list node.

In practical terms, if you don't implement a LinkedList class, the pointer to a linked list node could be the linked list itself, or a sublist. So std::vector<Node<int>*> would then be a vector of lists.

For example, you could implement mergeKLists in a way that joins all the linked lists in listArray together.

[Demo]

#include <fmt/core.h>
#include <vector>

template <typename T>
struct Node {
    T data;
    Node* next;
};

void mergeKLists(std::vector<Node<int>*>& listArray) {
    if (listArray.empty()) {
        return;
    }
    for (size_t i{ 0 }; i < listArray.size() - 1;   i) {
        auto ptr{ listArray[i] };
        while (ptr->next) {
            ptr = ptr->next;
        }
        ptr->next = listArray[i 1];
    }
}

void printList(const Node<int>* list) {
    fmt::print("[ ");
    for (auto ptr{ list }; ptr != nullptr; ptr = ptr->next) {
        fmt::print("{} ", ptr->data);
    }
    fmt::print("]");
}

int main() {
    Node<int> m2{2, nullptr};
    Node<int> m1{1, &m2};
    Node<int> n2{4, nullptr};
    Node<int> n1{3, &n2};
    std::vector<Node<int>*> lA{ &m1, &n1 };
    mergeKLists(lA);
    printList(lA[0]);
}

// Outputs: [ 1 2 3 4 ]

Creating a LinkedList class, and doing some encapsulation work, would help to make the code simpler and easier to read:

[Demo]

template <typename T>
class LinkedList {
public:
    LinkedList(Node<T>* head)
        : head_{ head }
    {}
    auto head() const {
        return head_;
    }
    auto head() {
        return head_;
    }
    auto tail() {
        auto ptr{ head_ };
        while (ptr and ptr->next) {
            ptr = ptr->next;
        }
        return ptr;
    }
    friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& l) {
        os << "[ ";
        for (auto ptr{ l.head() }; ptr != nullptr; ptr = ptr->next) {
            os << ptr->data << " ";
        }
        return os << "]";
    }
private:
    Node<T>* head_;
};

template <typename T>
using LinkedListVector = std::vector<LinkedList<T>>;

template <typename T>
void mergeKLists(LinkedListVector<T>& v) {
    if (v.empty()) {
        return;
    }
    for (size_t i{ 0 }; i < v.size() - 1;   i) {
        v[i].tail()->next = v[i 1].head();
    }
}