題目1：矩陣置零

題目：

問題分析：使用兩個布爾數組來分別記錄哪行哪列出現了0，當出現0的行和列，對應的布爾數組值置為true。再次遍歷數組，當出現行數組和列數組中的值為true，則對應的原數組的值置為0.

代碼：

class Solution {public void setZeroes(int[][] matrix) {int m=matrix.length;//記錄數組的行數int n=matrix[0].length;//記錄數組的列數boolean[] row=new boolean[m];boolean[] col=new boolean[n];for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(matrix[i][j]==0){row[i]=col[j]=true;}}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(row[i]||col[j]) matrix[i][j]=0;}}}
}

時間復雜度：O(mn).

題目2：螺旋矩陣

題目：

問題分析：用數組記錄四個方向，用「行偏移量，列偏移量」描述 4 個方向，directions的四個元素分別表示右 下 左 上四個方向，用directionIndex來訪問方向數組中的四個方向，是directions數組的索引，當遇到已訪問的數組元素或是邊界的時候，就更改訪問的方向為下一個方向。

代碼：

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result=new ArrayList<>();int rows=matrix.length;//總共的行數int columns=matrix[0].length;//總共的列數boolean[][] visited=new boolean[rows][columns];if(matrix==null||rows==0||columns==0){return result;}int row=0;//當前行int column=0;//當前列int[][] directions={{0,1},{1,0},{0,-1},{-1,0}};//分別表示右 下 左 上四個方向int directionIndex=0;//當前的方向索引，對上上面的數組directions的四個方向for(int i=0;i<rows*columns;i++){result.add(matrix[row][column]);visited[row][column]=true;int nextRow=row+directions[directionIndex][0];int nextColumn=column+directions[directionIndex][1];if(nextRow<0||nextRow>=rows||nextColumn<0||nextColumn>=columns||visited[nextRow][nextColumn]){directionIndex=(directionIndex+1)%4;//越界或是遇到已訪問的元素，方向換一個}row=row+directions[directionIndex][0];column=column+directions[directionIndex][1];}return result;}
}

時間復雜度：O(N).

題目3：旋轉圖像

題目：

問題分析：使用翻轉操作代替旋轉操作，先將數組以水平軸翻轉，再將數組根據對角線翻轉。水平翻轉只翻轉上半部分，所以i<n/2，對角線翻轉只翻轉一半的對角線，所以j<i.

代碼：

class Solution {public void rotate(int[][] matrix) {int n=matrix.length;for(int i=0;i<n/2;i++){//只翻轉上半部分for(int j=0;j<n;j++){int temp=matrix[i][j];matrix[i][j]=matrix[n-i-1][j];//水平翻轉，行變列不變matrix[n-i-1][j]=temp;}}for(int i=0;i<n;i++){for(int j=0;j<i;j++){int temp=matrix[i][j];matrix[i][j]=matrix[j][i];//對角線翻轉，行列互換matrix[j][i]=temp;}}}
}

時間復雜度：O(N^2).

題目4：搜索二維矩陣II

題目：

---

問題分析：從右上角開始查找，若當前元素大于target，則說明當前元素所在列都不可能找到target，因為數組從上到下升序排列，則往前一列繼續查找；若當前元素小于target，則說明當前元素所在行都不可能找到target，因為數組從左到右升序排列，則往下一行繼續查找。

代碼：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int i=0;int j=matrix[0].length-1;//右上角的數組下標while(i<matrix.length&&j>=0){if(matrix[i][j]==target) return true;//找到則返回trueelse if(matrix[i][j]>target){j--;}else{i++;}}return false;}
}

時間復雜度：O(M+N).

題目5：相交鏈表

題目：

問題分析：

代碼：

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p=headA;ListNode q=headB;while(p!=q){//p不等于q的時候才循環，p=q則證明要么到相交節點了，要么沒有相交節點，到空節點了p=p!=null?p.next:headB;q=q!=null?q.next:headA;}return p;}
}

代碼比較兩個節點的時候，比較的是內存地址是否一致，兩個鏈表相交，其相交節點的內存地址一定一致。

時間復雜度：O(M+N).

題目6：環形鏈表

題目：

問題分析：使用快慢指針來求解，快慢指針同時從頭結點出發，快指針每次走兩步，慢指針每次走一步，若是兩者相遇，這則證明鏈表中一定存在環。因為快指針相對于慢指針走一步，所以若有環，快指針一定會追上慢指針。

代碼：

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){//因為快指針每次走兩步，得同時滿足fast和fast.next都不為null的情況下，才能成功的走完兩步slow=slow.next;fast=fast.next.next;if(slow==fast){return true;}}return false;}
}

時間復雜度：O(N).

題目7：反轉鏈表

題目：

問題分析：使用迭代的頭插法來解決這道題目，例如鏈表1->2->3，使用頭插法，就是把新建一個空鏈表，依次把1,2,3插到這個新鏈表的頭部，就得到鏈表3->2->1，這就是反轉后的鏈表。

代碼：

class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null){return head;}ListNode pre=null;ListNode cur=head;while(cur!=null){ListNode next=cur.next;cur.next=pre;pre=cur;cur=next;//不斷地迭代，直至跳出while循環}return pre;}
}

時間復雜度：O(N).

題目8：回文鏈表

題目：

問題分析：首先找到鏈表的中間節點，若是原鏈表有奇數個節點，則是最中間一個，例如1->2->3,這個鏈表的中間節點是2；若是原鏈表有偶數個節點，則是中間偏右的那個節點，5->3->4->1，這個鏈表的中間節點是4。然后把中間節點之后的鏈表進行反轉，再依次比較反轉后的鏈表的各個節點與原鏈表前半部分節點的值。例如，原鏈表為6->4->5->4->6，中間的節點為5，反轉后的鏈表為head2: 6->4，之前的鏈表head: 6->4->5，比較各個節點的值。

代碼：

class Solution {public boolean isPalindrome(ListNode head) {ListNode mid=middleNode(head);ListNode head2=reverse(mid);while(head2!=null){if(head.val!=head2.val) return false;head=head.next;head2=head2.next;}return true;}private ListNode middleNode(ListNode head){ListNode slow=head;ListNode fast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}private ListNode reverse(ListNode head){ListNode pre=null;ListNode cur=head;while(cur!=null){ListNode next=cur.next;cur.next=pre;pre=cur;cur=next;}return pre;}
}

時間復雜度：O(N).