继续向前，很快九月份就到了！第三波。。
亮剑语录：
“天下没有打不破的包围圈，对我们独立团来说，老子就不把它当成是突围战，当成什么？当成进攻。向我们正面的敌人发起进攻，记住，全团哪怕只剩一个人，也要继续进攻，死也要死在冲锋的路上。”
20.链表中倒数第 K 个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路：
这题在leetcode中也有出现，之前也做过，我的思路是首先遍历一次求链表的长度，然后再重新遍历到 倒数第k个结点，这样的话需要遍历2次。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null ) return null;
int length = 1;
ListNode temp = head;
while (temp.next != null) {
length++;
temp = temp.next;
}
if (k > length || k <= 0) return null;
for (int i = 0; i < length - k ; i++) {
head = head.next;
}
return head;
}
}也可以只做到遍历一次，就是让first 指针先走k步，然后让first指针和second指针一起走，知道first指针指向为空。需要注意的就是k的取值不能大于链表长度，这里要判断。
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null) return null;
ListNode first = head;
ListNode second = head;
if (k <= 0) return null;
for (int i = 0; i < k; i++) {
if (first == null) return null;
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
return second;
}
}21. 链表中环的入口结点
题目描述：
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
解题思路：
利用双指针法，一个走一步slow，一个走两步fast，然后当两者首次相遇时，利用数学逻辑可以推断出，此时将fast 设置为头节点，然后两者再次同时前进一步，如果再次相遇，那么这个点就是环的入口节点。
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead){
if (pHead == null || pHead.next == null) return null;
ListNode fast = pHead;
ListNode slow = pHead;
while (fast.next.next != null && slow.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = pHead;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}22. 反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
解题思路：
使用头插法，将所有节点的next指向前一个节点
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode newList = new ListNode(-1);
while (head != null) {
ListNode next = head.next;
head.next = newList.next;////将当前节点对下一个节点的引用指向前一个节点
newList.next = head;////将前一个节点指向当前节点
head = next;
}
return newList.next;
}
}也可以使用递归：
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
head.next = null;
ListNode newHead = ReverseList(next);
next.next = head;
return newHead;
}
}24. 合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
解题思路：
迭代两个链表，然后进行比较，哪一个比较小就在前面，需要注意的就是需要有个临时节点newList
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode head = new ListNode(0);
ListNode newList = head;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
newList.next = list1;
list1 = list1.next;
}
else {
newList.next = list2;
list2 = list2.next;
}
newList = newList.next;
if (list1 == null) {
newList.next = list2;
}
if (list2 == null) {
newList.next = list1;
}
}
return head.next;
}
}也可以使用递归，更加简洁方便。。
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val < list2.val) {
list1.next = Merge(list1.next,list2);
return list1;
} else {
list2.next = Merge(list1,list2.next);
return list2;
}
}
}25. 树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路：
递归思想，当出现树总要考虑递归，方便，这里isSame为判断两个节点是否相同，这里需要注意t2为空时是一种子结构，应返回true。
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if (root1 == null || root2 == null) return false;
return isSame(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
private boolean isSame(TreeNode t1,TreeNode t2) {
if (t2 == null) return true; //t2为空时为子结构，返回真
if (t1 == null) return false; //t1为空时直接返回false
if (t1.val != t2.val) return false;
return isSame(t1.left,t2.left) && isSame(t1.right,t2.right);
}
}26. 二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5 解题思路：同样考虑使用递归来解决问题，中间部分为交换左右节点的代码，后面递归。
public class Solution {
public void Mirror(TreeNode root) {
if (root == null) return;
TreeNode temp = null;
temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}27. 对称的二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
二叉树的镜像可以参考26题
解题思路：重载方法isSymmetrical，然后判断，递归。
public class Solution {
boolean isSymmetrical(TreeNode pRoot){
if (pRoot == null) return true;
return isSymmetrical(pRoot.left,pRoot.right);
}
boolean isSymmetrical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
if (t1.val != t2.val) return false;
return isSymmetrical(t1.left,t2.right) && isSymmetrical(t1.right,t2.left);
}
}28. 顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路：
分别从四个方向开始遍历放进链表中
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
int m1 = 0;
int m2 = matrix.length - 1;
int n1 = 0;
int n2 = matrix[0].length - 1;
ArrayList<Integer> list = new ArrayList<>();
while (m1 <= m2 && n1 <= n2) {
// 从左到右
for (int i = m1; i <= n2; i++) {
list.add(matrix[m1][i]);
}
// 从上到下
for (int i = m1+1; i <= m2; i++) {
list.add(matrix[i][n2]);
}
//从右到左
if (m1 != m2) {
for (int i = n2 - 1; i >= n1; i--){
list.add(matrix[m2][i]);
}
}
// 从下到上
if (n1 != n2) {
for (int i = m2 - 1; i > m1; i--)
list.add(matrix[i][n1]);
}
m1++; m2--; n1++; n2--;
}
return list;
}
}29. 包含min函数的栈
题目描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
解题思路：使用一个最小元素栈， 每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出的元素和最小元素栈的栈顶元素相等, 就把最小元素的栈顶弹出.
import java.util.Stack;
public class Solution {
public Stack<Integer> stack = new Stack<>();
public Stack<Integer> minStack = new Stack<>();
public void push(int node) {
stack.push(node);
if (minStack.isEmpty()) {
minStack.push(node);
} else if (node <= minStack.peek()){
minStack.push(node);
}
}
public void pop() {
if (minStack.peek() == stack.pop()) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}这周回学校报到了，这十道刷的有点久，要加快进度了呀。。
