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;
}
}
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAnYldHL0FWby9mZvwFN4ETMfdHLkVGepZ2XtxSZ6l2clJ3LcV2Zh1Wa9M3clN2byBXLzN3btgHL9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsQTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5CN3QTN3ATYwYmM5ATM0EjNzYzX1QzM1MjMxAzLcFTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
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
思路
这里直接用官方题解中的图,也是借助一个辅助栈来实现,题解十分通俗易懂,如下图:
(下图来源)
可能代码中唯一不好理解的地方,是这里:
实现
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();
}
}