Linked List Matrix

JavaView on GFG

Time: O(n*m)

Space: O(n*m)

Intuition

Construct a linked list from matrix in diagonal order. Traverse diagonals from bottom-left to top-right.

Algorithm

1Collect diagonals (d = row+col is constant per diagonal). Sort diagonals by index.
2Link nodes in order: diagonal 0, then 1, etc.

Common Pitfalls

•Each diagonal has d = row+col. Within diagonal: row decreases as col increases. Build linked list in traversal order.

Linked List Matrix.java

Java

// Approach: Traverse matrix row by row, left-to-right, top-to-bottom, creating linked list nodes.
// Time: O(n*m) Space: O(n*m)
class Node {
    int data;
    Node right, down;

    Node(int data) {
        this.data = data;
        right = null;
        down = null;
    }
}

class Solution {
    static Node construct(int arr[][]) {
        Node head = new Node(arr[0][0]);
        Node node = head;
        for (int row = 0; row < arr.length; row++) {
            Node curr = node;
            for (int col = 0; col < arr[0].length; col++) {
                if (col + 1 < arr[0].length)
                    curr.right = new Node(arr[row][col + 1]);
                if (row + 1 < arr.length)
                    curr.down = new Node(arr[row + 1][col]);
                curr = curr.right;
            }
            node = node.down;
        }
        return head;
    }
}

Was this solution helpful?