Question

How to construct a linked list from a 2d matrix with pointers to the right and down in C++

Answer 1

#include <iostream>

#define SIZE 3

using namespace std;

// Define the structure for a node
struct Node {
    int data;
    Node* right;
    Node* down;

    Node(int value) : data(value), right(nullptr), down(nullptr) {}
};

// Function to construct a 2D linked list from a 2D matrix
Node* constructLinkedList(int matrix[][SIZE], int rows, int cols) {
    Node* head = nullptr;
    Node* prevRow = nullptr;

    for (int i = 0; i < rows; i++) {
        Node* rowHead = nullptr;
        Node* prevNode = nullptr;

        for (int j = 0; j < cols; j++) {
            Node* newNode = new Node(matrix[i][j]);

            if (!rowHead) rowHead = newNode; // Set the head of the current row
            if (prevNode) prevNode->right = newNode; // Link the previous node in the row

            if (prevRow) prevRow->down = newNode; // Link the node above in the column

            prevNode = newNode;
            if (prevRow) prevRow = prevRow->right; // Move to the next node in the previous row
        }

        if (!head) head = rowHead; // Set the head of the entire linked list
        prevRow = rowHead; // Move to the next row
    }

    return head;
}

// Function to print the 2D linked list
void printLinkedList(Node* head) {
    Node* row = head;

    while (row) {
        Node* col = row;
        while (col) {
            cout << col->data << " ";
            col = col->right;
        }
        cout << endl;
        row = row->down;
    }
}

// Function to free the 2D linked list
void freeLinkedList(Node* head) {
    Node* row = head;

    while (row) {
        Node* col = row;
        while (col) {
            Node* temp = col;
            col = col->right;
            delete temp;
        }
        row = row->down;
    }
}

int main() {
    int matrix[SIZE][SIZE] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    Node* head = constructLinkedList(matrix, SIZE, SIZE);
    
    printLinkedList(head);
    freeLinkedList(head); // Clean up memory
}


/*
run:

1 2 3 
4 5 6 
7 8 9 

*/

 

70+ SQL courses for beginners and professionals