JZ15 反转链表
（中等）
题目
描述
输入一个链表，反转链表后，输出新链表的表头。
示例1
输入：
{1,2,3}
返回值：
{3,2,1}
思路
这也是一道经典的链表题目，借助栈结构便可以实现，我们遍历链表中的结点，并且按顺序压入栈中（注意，因为链表中的结点都有 next 属性值，我们应自己去创建一个等 val 值的结点，而不能直接用链表中的结点），之后我们创建一个辅助用的头结点，将栈中的结点出栈，并加入到头结点之后，这样，由于栈结构先进后出的特点，我们最终得到新的链表自然就为原链表的逆序链表。 当想清楚主要思路后，也要考虑好特殊情况，如参数 head 为 null 时，我们需要返回 null，使代码有较强的健壮性，当传入的链表只有一个结点时，那么链表的反转也还是为自身，也就是此结点。
实现
public class JZ15反转链表 {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
Stack<ListNode> stack = new Stack<ListNode>();
while (head != null) {
stack.push(new ListNode(head.val));
head = head.next;
}
ListNode newHead = new ListNode(-1);
ListNode temp = newHead;
while (!stack.isEmpty()) {
temp.next = stack.pop();
temp = temp.next;
}
return newHead.next;
}
}
JZ21 栈的压入、弹出序列
（中等）
题目
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
示例
输入：
[1,2,3,4,5],[4,3,5,1,2]
返回值：
false
思路
这里直接用官方题解中的图，也是借助一个辅助栈来实现，题解十分通俗易懂，如下图：
（下图来源）
可能代码中唯一不好理解的地方，是这里：
这是在当 pushA[i] = popA[j] 时，说明这个元素是放入栈中立马弹出，所以，++i, ++j，从而直接略过这个元素的进栈和出栈即可，而又因为当前 pushA 数组中的的 i 值不一定再是正好对应栈顶元素，而可能在这个 i 元素入栈之前也执行了出栈，而且不一定只是 1 次，因此，便需要直接利用 top 方法取得栈顶元素，并使其与当前出栈元素比较，若相等，则让辅助栈的栈顶元素出栈，并让出栈数组右移一个下标即可，再进行判断，直到当前出栈的不是当前栈顶或是当前栈已经为空，也就是进栈的元素都已出栈。
实现
public class JZ21栈的压入弹出序列 {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<Integer>();
int i = 0, j = 0;
while (i < pushA.length) {
if (pushA[i] != popA[j]) {
stack.push(pushA[i]);
i++;
} else { //当 pushA[i] = popA[j]
i++; j++;
while (!stack.isEmpty() && stack.peek() == popA[j]) {
stack.pop();
j++;
}
}
}
return stack.isEmpty();
}
}
