Construct LinkedList - C++ Solution

1. Introduction

In this blog post, we'll explore how to implement a fundamental data structure operation in C++: constructing a linked list from an array of integers. This problem is a basic application of linked list manipulation, where each element of the array becomes a node in the linked list.

Problem

Given an array of integers, the objective is to create a linked list where each element of the array becomes a node. The nodes should be inserted at the front of the list.

Example:

Input: [1, 2, 3, 4, 5]

Output: 1 —> 2 —> 3 —> 4 —> 5 —> nullptr

2. Solution Steps

1. Define a ListNode structure to represent each node in the linked list.

2. Iterate over the array and for each element:

a. Create a new node.

b. Insert the new node at the front of the linked list.

3. Return the head of the linked list.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Define the ListNode structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to construct a linked list from an array
ListNode* constructLinkedList(const vector<int>& keys) {
    ListNode *head = nullptr;

    // Iterate over the array and insert each key at the front
    for (int key : keys) {
        ListNode *newNode = new ListNode(key);
        newNode->next = head;
        head = newNode;
    }

    return head;
}

// Function to print the linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " —> ";
        head = head->next;
    }
    cout << "nullptr\n";
}

int main() {
    vector<int> keys = {1, 2, 3, 4, 5};
    ListNode *listHead = constructLinkedList(keys);
    printLinkedList(listHead);
    return 0;
}

Output:

1 —> 2 —> 3 —> 4 —> 5 —> nullptr

Explanation:

The constructLinkedList function iteratively constructs a linked list from the given array. It creates a new ListNode for each key in the array and inserts it at the front of the list. The printLinkedList function is used to display the constructed list, showing the elements in the order they appear in the array. The implementation demonstrates basic linked list operations in C++, creating a straightforward representation of the array as a linked list.