Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Solution1(leetcode上最后一个testcase没过): 如果矩阵只有一行或者一列，那么无需转圈，依次输出即可。其他情况均需转圈：从左到右，从上到下，从右到左，从下到上。如果奇数行，中心点要单独加。

public class Solution {
    public ArrayList spiralOrder(int[][] matrix) {
        ArrayList result = new ArrayList();

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return result;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        while(top <= bottom && left <= right) {
            if(m == 1) {
                for(int i = 0; i < n; i++) {
                    result.add(matrix[0][i]);
                }
                break;
            }else if(n == 1) {
                for(int i = 0; i < m; i++) {
                    result.add(matrix[i][0]);
                }
                break;
            }
        
            for(int i = left; i < right; i++) {
                result.add(matrix[top][i]);
            }
            for(int i = top; i < bottom; i++) {
                result.add(matrix[i][right]);
            }
            for(int i = right; i > left; i--) {
                result.add(matrix[bottom][i]);
            }
            for(int i = bottom; i > top; i--) {
                result.add(matrix[i][left]);
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        
        if(n % 2 != 0 && m == n && m > 1)
            result.add(matrix[n/2][n/2]);

        return result;
    }
}

Solution2: 
类似于rotate image的做法。Run time complexity is O(m * n), space complexity is O(n), 储存结果占用的空间.

public class Solution {
    public List spiralOrder(int[][] matrix) {
        List res = new ArrayList();
        if (matrix == null || matrix.length == 0) {
            return res;
        }
        
        int min = Math.min(matrix.length, matrix[0].length);
        int level = min / 2;
        for (int i = 0; i < level; i++) {
            for (int j = i; j < matrix[0].length - i - 1; j++) {
                res.add(matrix[i][j]);
            }
            
            for (int j = i; j < matrix.length - i - 1; j++) {
                res.add(matrix[j][matrix[0].length - i - 1]);
            }
            
            for (int j = matrix[0].length - i - 1; j > i; j--) {
                res.add(matrix[matrix.length - i - 1][j]);
            }
            
            for (int j = matrix.length - i - 1; j > i; j--) {
                res.add(matrix[j][i]);
            }
        }
        
        if (min % 2 != 0) {
            if (matrix.length < matrix[0].length) {
                for (int i = level; i < matrix[0].length - level; i++) {
                    res.add(matrix[level][i]);
                }
            } else {
                for (int i = level; i < matrix.length - level; i++) {
                    res.add(matrix[i][level]);
                }
            }
        }
        
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/21667181