思路： 题目所给的是单链表，想了一下反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，......，第二个指向第一个，第一个指向null; 知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。 这就需要把结点挨个从链表上摘下来，做调整； 这个调整过程需要两个指针辅助：pre记录其前一个结点位置，好让该结点的next指针指向前一个结点，但是在指向前一个结点前需要用一个指针p记录后一个结点地址，避免结点丢失。 例子： 以head结点为例步骤如下： 1.反转后head是指向null，所以未反转的时候其前一个结点应该是null，初始化pre指针为null； 2.用...

思路： 开辟新数组保存法：创建两个数组，一个用来存奇数，一个用来存偶数，最后合并。 不开辟新数组： 1.用两个下标i,j进行遍历; 2.当i走到偶数时停下，并让j从i的后一个元素开始遍历；(若i走到队尾则循环结束) 3.若j所指的是偶数则继续前进，j遇到奇数则停下(如果j都没遇到奇数则在队尾停下，结束。)。 4.此时j所指的是奇数，i所指的是偶数(i到j-1都是偶数)。 5.则可以用临时变量temp保存j对应的值，然后从j-1开始到i，挨个后移一位。 6.将temp保存的值插入到i的位置。 优化：冒泡排序也可以保证相对位置不变，所以用冒泡排序写起来会更方便。 答案： 不开辟新数组：...

思路： 1.利用一个结论：一个二进制数n减1后与原二进制数进行&运算( 即n&(n-1) )会消去最右边的1。2.这个结论怎么来的？ 假设二进制数101进行减1运算，刚好最右边是1，则得到100，此时用100跟101做&运算，得到的是100，故消去了101左右边的1。 100减1呢？最低位是0,跟十进制减法一样啊，向高位借。(可以脑补一下十进制100减1的过程) 所以二进制100减1的运算过程如下： 最右边的0向右数第二位借1得：2-1=1， 右数第二位还是0，却要借给最右边那位1，所以它也得向高位借。 这样右数第三位的1借给它1之后变成0，右数第二位借1得：2...

思路： 斐波那契数列：0,1,1,2,3,5...F(n-2),F(n-1),F(n)=F(n-2)+F(n-1) 递归 用数组来保存fibonacci数列,然后根据输入的n返回数组下标为n处的值。 根据斐波那契数列的公式，可以用3个变量来表示(也可以只用两个变量) 答案： 1.递归 public class Solution { public int Fibonacci(int n) { if(n <= 1){ return n; } return Fibonacci(n-1)+Fibonacci(n-...

思路： 首先要明确队列的特性是先进先出，栈的特性是先进后出； 在进队列的方法里我们只要有容器能装元素就行了，所以直接往栈1里压； 在出队列方法里，要保证出队列的是最先进入的元素： 最直观的想法就是把栈1的元素挨个出栈，然后往栈2里压。 但是还是要思考一下真的这么简单吗？不是的，栈2为空时才允许栈1往外弹元素并压到栈2里。 如果随时都可以往栈2里压，那么往栈1里压两个元素5、6（栈1状态是：{5,6}），马上出栈往栈2里压（栈2状态：{6,5}）； 接着栈1又来了个元素7，栈2的元素5、6还没出栈，此时要是再把7压到栈2那么栈顶元素就变7了，没法先取出5； 所以在往栈2压完一批元素后，栈1...

思路： 前序遍历：根→左→右中序遍历：左→根→右 由前序遍历序列pre={1,2,4,7,3,5,6,8}可知根结点是1； 则在中序遍历序列in={4,7,2,1,5,3,8,6}中找到1，便可知1所在位置的左侧是左子树,1所在位置的右侧是右子树； 递归调用：将左子树和右子树分别看成一颗树，将其前序遍历序列、中序遍历序列分别传入到该方法中，便可得到左子树的根结点、右子树的根结点。此时需要用第一步得到的根结点连接它们； 递归调用的终止条件：直到传入数组为空，说明已经没有节点，直接返回null。 答案： import java.util.Arrays; public class Solutio...

思路 1.递归；2.利用Java List的add(int index,Integer element)；3.利用栈的先进后出4.用Collections.reverse(List<?> list); 答案 1.递归 import java.util.ArrayList; public class Solution { ArrayList<Integer> arrayList = new ArrayList<Integer>(); public ArrayList<Integer> printListFromTailToHead(...

思路： 解法一：用Java自带的函数str.toString().replace(" ","%20")。 解法二：在当前字符串上进行替换。 先计算替换后的字符串需要多大的空间，并对原字符串空间进行扩容； 从后往前替换字符串的话，每个字符串只需要移动一次； 如果从前往后，每个字符串需要多次移动，效率较低。 解法三：开辟一个新的字符串。 答案： 在当前字符串上进行从后往前的替换： public class Solution { public String replaceSpace(StringBuffer str) { int spacenum = 0; ...

思路： 暴力解法：对数组第一行进行二分查找，再对数组第二行进行二分查找。 矩阵是有序的：利用二维数组由上到下，由左到右递增的规律。那么选取右上角或者左下角的元素a[row][col]与target进行比较，当target小于元素a[row][col]时，那么target必定在元素a所在列的左边,即col--；当target大于元素a[row][col]时，那么target必定在元素a所在行的下边,即row++。 答案： 取数组左下角的元素开始比较： public class Solution { public boolean Find(int target, int [][] ar...

思路： 带头结点还是不带头结点的链表？不用纠结，随便确定一个，就以不带头结点为例。 首先想到的是用两个指针遍历链表。一个走的快遍历整个链表并统计出链表有多少个结点；另一个是达到一定条件开始遍历链表，当快指针遍历完整个链表的时候，慢指针刚好停在我们需要的倒数第K个。 那我们就需要确定几个条件，快指针是走到最后一个结点停下，还是走到最后一个结点后面的空结点停下？这将决定了我们的慢指针什么时候开始走。 答案： 以快指针走到null停下为例：快指针停在null，慢指针刚好停在倒数第K个结点。此时就它两的距离是K，所以我们设置慢指针开始走的条件应该是快指针走了K步之后。第K+1步的时候，快慢指针一起...