Сформируйте прямоугольник из граничных элементов матрицы, используя связанный список

Дана матричная сетка [][] размером NxM, где N — количество строк, а M — количество столбцов. Задача состоит в том, чтобы сформировать прямоугольник из граничных элементов grid[][] с помощью связанного списка, имеющего четыре указателя, а именно prev , next , top и bottom . Распечатайте окончательный связанный список.

Примеры:

Input: A = [[13, 42, 93, 88], 
                  [26, 38, 66, 42], 
                 [75, 63, 78, 12]]
Output: 13 42 93 88 42 12 78 63 75 26

Explanation:  
 

1. Make A[0][0] and head node
2. Traverse through 0th row and create node for each element and connect them through next pointer.
3. Traverse through (m-1)th column and create node for each element and connect them through bottom pointer.
4. Traverse through (n-1)th row and create node for each element and connect them through prev pointer.
5. Traverse through 0th column and create node for each element and connect them through top pointer.
6. Step 2, 3, 4, 5 is repeated till temp. The top become equal to head.

Input: A = [[1, 2, 3]
                  [8, 9, 4]
                 [7, 6, 5]]
Output: 1 2 3 4 5 6 7 8

Подход: эту проблему можно решить, выполнив обход границы матрицы и создав узлы для каждого элемента и связав их, используя следующий, предыдущий, нижний или верхний и создав связанный список.

Выполните следующие действия:

Шаг 1: Сделайте grid[0][0] заголовком связанного списка и инициализируйте temp в качестве заголовка .
Шаг 2: Пройдите через первую строку от j=1 до j=m-1, где i=0 , создайте узел для каждого элемента и свяжите их через следующий указатель.
Шаг 3: Пройдите по последнему столбцу от i=0 до i=n-1, где j=m-1 , создайте узел для каждого элемента и свяжите их через нижний указатель.
Шаг 4: Пройдите последнюю строку от j=m-1 до j=0 , где i=n-1 , создайте узел для каждого элемента и свяжите их с помощью указателя prev .
Шаг 5: Пройдите через первый столбец от i=n-1 до i=0 , где j=0 , и создайте узел для каждого элемента и свяжите их через верхний указатель.
Шаг 6: Шаги 2, 3, 4, 5 повторяются до тех пор, пока temp.top не станет равным head .
Шаг 7: Распечатайте необходимый связанный список.

Ниже приведена реализация вышеописанного алгоритма.

Временная сложность: O(N*M)
Вспомогательное пространство: O(N*M)