CareerCup

This can be done recursively for any m x n matrix. It does not matter if m and n are same or not.

I am giving the code for a singly linked list, but this can easily be extended to doubly linked list:

C#:

public class Node
{
	public int data;
	public Node right;
	public Node down;
}
private Node head;


// Wrapper method that calls the recursive method
// to create linked list out of matrix
public void ProcessMatrix(int[][] matrix)
{
	head=ConvertToLL(matrix,0,0);
}

// i=row, j=col
public Node ConvertToLL(int[][] matrix, int i, int j)
{
	if(i>matrix.Length) return null;	// i > available rows
	if(j>matrix[i].Length) return null;	// j > available cols
	
	Node node=new Node() { data=matrix[i][j] };  // using automatic initializers
	node.right=CovertToLL(matrix, i, j+1);
	node.down=ConvertToLL(matrix, i+1, j);

	return node;
}

My code :

//
//  main.cpp
//  ListListFromMatrix
//
//  Created by Srikant Aggarwal on 10/01/12.
//  Copyright 2012 NSIT. All rights reserved.
//

#include <iostream>

using namespace std;

typedef struct node
{
    int data;
    struct node *right;
    struct node *down;
}node;

int main (int argc, const char * argv[])
{
    int n, m;
    int i = 0;
    
    cin >> n >> m;
    
    int **arr = new int *[n];
    while(i < n)
    {
        arr[i] = new int[m];
        i++;
    }
    
    int j = 0;
    i = 0;
    
    while(i < n)
    {
        while(j < m)
        {
            cin >> arr[i][j];
            j++;
        }
        j = 0;
        i++;
    }
    
    node *parent = NULL, *child = NULL;
    node *start = NULL;
    
    i = 0;
    while(i < n)
    {
        j = 0;
        node *head = NULL;
        while(j < m)
        {
            node *temp = new node;
            temp->data = arr[i][j];
            temp->right = temp->down = NULL;
            
            if(head == NULL)
            {
                head = temp;
                if(start == NULL)
                    start = head;
            }
            else
                child->right = temp;
                
            if(parent != NULL)
            {
                parent->down = temp;
                parent = parent->right;
            }
            
            child = temp;
            j++;
        }
        
        parent = head;
        j = 0;
        i++;
    }
    
    node *curr_ver_node = start;
    while(curr_ver_node != NULL)
    {
        node *curr_hor_node = curr_ver_node;
        while(curr_hor_node != NULL)
        {
            cout << curr_hor_node->data << " ";
            curr_hor_node = curr_hor_node->right;
        }
        cout << endl;
        curr_ver_node = curr_ver_node->down;
    }
    
    return 0;
}

#include "stdafx.h"
#include <cstring>
#include <cstdlib>
#include <cstdio>

struct Node
{
double data;
Node *right;
Node *down;
Node()
{
right =NULL;
down =NULL;
}
};
int m, n;
Node* convertMaxtrixToList(double matrix[4][4])
{
Node *root;
Node *last_top_left_node =NULL;
for (int i=0;i<m;i++)
{
Node *top_left_node =new Node();
top_left_node->data =matrix[i][i];
if (i==0)
root =top_left_node;
Node *pre_node =top_left_node;
for (int j=i+1;j<n;j++)
{
Node *node =new Node();
node->data = matrix[i][j];
pre_node->right =node;
pre_node =node;

}
pre_node =top_left_node;
for (int j =i+1;j<n;j++)
{
Node *node =new Node();
node->data = matrix[j][i];
pre_node->down =node;
pre_node =node;
}
if (last_top_left_node)
{
Node *tmp =last_top_left_node ->right;
for (Node *node =top_left_node;node;node=node->right, tmp =tmp->right)
{
tmp->down =node;
}

tmp=last_top_left_node ->down;
for (Node *node =top_left_node;node;node=node->down, tmp =tmp->down)
{
tmp->right =node;
}
}
last_top_left_node =top_left_node;
}
return root;
}

void print(Node *root)
{
for (Node *i =root;i;i=i->down)
{
for (Node *j=i;j;j=j->right)
{
printf("%lf ", j->data);
}
printf("\n");
}
}

int main ()
{
double matrix[4][4];
memset(matrix, 0, sizeof matrix);
m =4;
n =4;
Node *root = convertMaxtrixToList(matrix);
print(root);
return 0;
}

this boils down to serializing a linked list. the code and explanation is there in 'programming interviews exposed'