给定一个矩阵，任务是构造一个链表矩阵，其中每个节点都与其右下节点相连。 例子：
null
Input: [1 2 3 4 5 6 7 8 9]Output:1 -> 2 -> 3 -> NULL| | |v v v4 -> 5 -> 6 -> NULL| | |v v v7 -> 8 -> 9 -> NULL| | |v v vNULL NULL NULL
本文已经讨论了这个问题的递归解决方案 邮递 .以下是解决该问题的迭代方法：
- 其思想是创建m个链表（m=行数），每个节点存储其右节点。每m个链表的头指针存储在一个节点数组中。
- 然后，遍历m个列表，每个i和（i+1） th 列表中，设置i的每个节点的向下指针 th 列表到其对应的（i+1）节点 th 列表
![图片[1]-从2D矩阵构造链表（迭代法）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Construct-linked-list-from-matrix.jpg)
以下是上述方法的实施情况：
C++
// C++ program to construct a linked // list from 2D matrix | Iterative Approach #include <bits/stdc++.h> using namespace std; // struct node of linked list struct node { int data; node *right, *down; }; // utility function to create a new node with given data node* newNode( int d) { node* temp = new node; temp->data = d; temp->right = temp->down = NULL; return temp; } // utility function to print the linked list pointed to by head pointer void display(node* head) { node *rp, *dp = head; // loop until the down pointer is not NULL while (dp) { rp = dp; // loop until the right pointer is not NULL while (rp) { cout << rp->data << " " ; rp = rp->right; } cout << endl; dp = dp->down; } } // function which constructs the linked list // from the given matrix of size m * n // and returns the head pointer of the linked list node* constructLinkedMatrix( int mat[][3], int m, int n) { // stores the head of the linked list node* mainhead = NULL; // stores the head of linked lists of each row node* head[m]; node *righttemp, *newptr; // Firstly, we create m linked lists // by setting all the right nodes of every row for ( int i = 0; i < m; i++) { // initially set the head of ith row as NULL head[i] = NULL; for ( int j = 0; j < n; j++) { newptr = newNode(mat[i][j]); // stores the mat[0][0] node as // the mainhead of the linked list if (!mainhead) mainhead = newptr; if (!head[i]) head[i] = newptr; else righttemp->right = newptr; righttemp = newptr; } } // Then, for every ith and (i+1)th list, // we set the down pointers of // every node of ith list // with its corresponding // node of (i+1)th list for ( int i = 0; i < m - 1; i++) { node *temp1 = head[i], *temp2 = head[i + 1]; while (temp1 && temp2) { temp1->down = temp2; temp1 = temp1->right; temp2 = temp2->right; } } // return the mainhead pointer of the linked list return mainhead; } // Driver program to test the above function int main() { int m, n; // m = rows and n = columns m = 3, n = 3; // 2D matrix int mat[][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; node* head = constructLinkedMatrix(mat, m, n); display(head); return 0; } |
JAVA
// Java implementation for above approach // Construct a Linked List from 2-D Matrix class LinkedMatrix { class Node { int data; Node right, down; // Default Constructor Node() { this .right = null ; this .down = null ; } Node( int d) { this .data = d; this .right = null ; this .down = null ; } } /* A function to construct a Linked List from the given matrix of size m * n and returns the head pointer of the linked list */ Node constructLinkedMatrix( int [][] arr, int m, int n) { // stores the head of the linked list Node mainHead = null ; // stores the head of linked lists // of each row Node[] head = new Node[m]; Node rightTemp = new Node(), newptr; // Firstly, we create m linked lists // by setting all the right nodes of every row for ( int i = 0 ; i < m; i++) { // initially set the head of // ith row as NULL head[i] = null ; for ( int j = 0 ; j < n; j++) { newptr = new Node(arr[i][j]); // stores the mat[0][0] node as // the mainhead of the linked list if (mainHead == null ) mainHead = newptr; if (head[i] == null ) head[i] = newptr; else rightTemp.right = newptr; rightTemp = newptr; } } // Then, for every ith and (i+1)th list, // we set the down pointers of // every node of ith list // with its corresponding // node of (i+1)th list for ( int i = 0 ; i < m - 1 ; i++) { Node temp1 = head[i], temp2 = head[i + 1 ]; while (temp1 != null && temp2 != null ) { temp1.down = temp2; temp1 = temp1.right; temp2 = temp2.right; } } // return the mainhead pointer // of the linked list return mainHead; } // utility function to print the // linked list pointed to by head pointer void display(Node head) { Node rp, dp = head; // loop until the down pointer // is not NULL while (dp != null ) { rp = dp; // loop until the right pointer // is not NULL while (rp != null ) { System.out.print(rp.data + " " ); rp = rp.right; } System.out.println(); dp = dp.down; } } // Driver Code public static void main(String[] args) { LinkedMatrix Obj = new LinkedMatrix(); int m = 3 , n = 3 ; // m = rows and n = columns // 2-D Matrix int [][] arr = {{ 1 , 2 , 3 }, { 4 , 5 , 6 }, { 7 , 8 , 9 }}; Node head = Obj.constructLinkedMatrix(arr, m, n); Obj.display(head); } } // This code is contributed by Rhythem |
Python3
# Python3 program to construct a linked # list from 2D matrix | Iterative Approach # struct node of linked list class node: def __init__( self , data): self .data = data self .right = None self .down = None # utility function to create a new node with given data def newNode(d): temp = node(d) return temp; # utility function to print the linked list pointed to by head pointer def display(head): rp = None dp = head; # loop until the down pointer is not None while (dp ! = None ): rp = dp; # loop until the right pointer is not None while rp ! = None : print (rp.data, end = ' ' ) rp = rp.right; print () dp = dp.down; # function which constructs the linked list # from the given matrix of size m * n # and returns the head pointer of the linked list def constructLinkedMatrix(mat, m, n): # stores the head of the linked list mainhead = None ; # stores the head of linked lists of each row head = [ 0 for i in range (m)]; righttemp = None newptr = None # Firstly, we create m linked lists # by setting all the right nodes of every row for i in range (m): # initially set the head of ith row as None head[i] = None ; for j in range (n): newptr = newNode(mat[i][j]); # stores the mat[0][0] node as # the mainhead of the linked list if ( not mainhead): mainhead = newptr; if ( not head[i]): head[i] = newptr; else : righttemp.right = newptr; righttemp = newptr; # Then, for every ith and (i+1)th list, # we set the down pointers of # every node of ith list # with its corresponding # node of (i+1)th list for i in range (m - 1 ): temp1 = head[i] temp2 = head[i + 1 ]; while (temp1 and temp2): temp1.down = temp2; temp1 = temp1.right; temp2 = temp2.right; # return the mainhead pointer of the linked list return mainhead; # Driver code if __name__ = = '__main__' : m = 3 n = 3 ; # 2D matrix mat = [ [ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 7 , 8 , 9 ] ]; head = constructLinkedMatrix(mat, m, n); display(head); # This code is contributed by rutvik_56 |
C#
// C# implementation for above approach using System; // Construct a Linked List from 2-D Matrix class GFG { class Node { public int data; public Node right, down; // Default Constructor public Node() { this .right = null ; this .down = null ; } public Node( int d) { this .data = d; this .right = null ; this .down = null ; } } /* A function to construct a Linked List from the given matrix of size m * n and returns the head pointer of the linked list */ Node constructLinkedMatrix( int [,] arr, int m, int n) { // stores the head of the linked list Node mainHead = null ; // stores the head of linked lists // of each row Node[] head = new Node[m]; Node rightTemp = new Node(), newptr; // Firstly, we create m linked lists // by setting all the right nodes of every row for ( int i = 0; i < m; i++) { // initially set the head of // ith row as NULL head[i] = null ; for ( int j = 0; j < n; j++) { newptr = new Node(arr[i, j]); // stores the mat[0][0] node as // the mainhead of the linked list if (mainHead == null ) mainHead = newptr; if (head[i] == null ) head[i] = newptr; else rightTemp.right = newptr; rightTemp = newptr; } } // Then, for every ith and (i+1)th list, // we set the down pointers of // every node of ith list // with its corresponding // node of (i+1)th list for ( int i = 0; i < m - 1; i++) { Node temp1 = head[i], temp2 = head[i + 1]; while (temp1 != null && temp2 != null ) { temp1.down = temp2; temp1 = temp1.right; temp2 = temp2.right; } } // return the mainhead pointer // of the linked list return mainHead; } // utility function to print the // linked list pointed to by head pointer void display(Node head) { Node rp, dp = head; // loop until the down pointer // is not NULL while (dp != null ) { rp = dp; // loop until the right pointer // is not NULL while (rp != null ) { Console.Write(rp.data + " " ); rp = rp.right; } Console.WriteLine(); dp = dp.down; } } // Driver Code public static void Main(String[] args) { GFG Obj = new GFG(); int m = 3, n = 3; // m = rows and n = columns // 2-D Matrix int [,] arr = {{ 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 }}; Node head = Obj.constructLinkedMatrix(arr, m, n); Obj.display(head); } } // This code is contributed by PrinciRaj1992 |
输出：
1 2 3 4 5 6 7 8 9
时间复杂性： O（M*N）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
