题目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).