剑指offer ：删除链表的结点 && 包含min的栈

删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 示例 2:

输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：

直接遍历找到待删除的结点的前一个结点，删除即可。

问题在于：如果要删除的是头结点，比较麻烦

所以加一个哨兵结点简化编程

public ListNode deleteNode(ListNode head, int val) { // 如果头结点为空，直接返回 if (head == null) { return head; } // 临时节点，用来当做哨兵头 ListNode resPre = new ListNode(); resPre.next = head; ListNode p = head; // 记录上一个结点 ListNode last = resPre; // 找到要删除的节点 while (p != null) { // 找到要删除的节点了 if (p.val == val) { // 改变指向 last.next = p.next; // 清除这个结点内容以及指针 p.next = null; p = null; return resPre.next; } else { last = p; p = p.next; } } return resPre.next; }

剑指Offer本题：

给一个链表，给一个待删除的 结点。

给的是结点，不是值，表示我们可以通过 结点.next得到剩下的数据。

那么我们在不知道上一个结点只知道后面结点的情况下，如何删除当前节点呢。

答案是：我们可以复制，把后一个结点的值复制到前一个结点来，再修改当前节点的指针即可。

问题在于：如果待删除的是最后一个，我们还是需要遍历整个链表，得到最后一个结点的前一个。

public ListNode deleteNode(ListNode head, ListNode readToDel) { if (head == null) { return null; } // 如果要删除的恰好是头结点，且头结点的后面没结点了 if (head.next == null && readToDel == head) { head = null; return null; } ListNode next = readToDel; // 要删除的是尾结点 if (readToDel.next == null) { foreachToDel(head, readToDel); } else { // 要删除的是中间结点 ListNode next = readToDel.next; // 复制值和指向 readToDel.val = next.val; readToDel.next = next.next; // 清空next的指针 next.next = null; next = null; } } private void foreachToDel(ListNode head, ListNode readToDel) { ListNode pre = head; ListNode p = head; while (p != null && p != readToDel) { pre = p; p = p.next; } }

包含min的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：

要求的是O(1)时间复杂度。

经典的必定是空间换时间。

那么来吧。

每次插入元素和上一次的最小值比较即可。保存最小的。

下面有几个解法。

双栈

一个栈保存值

一个栈保存最小值

双栈组合。

本质还是双栈，只是把两个栈简化为一个对象放入一个栈而已。

不过因为这种解法可以把栈简化为对象，不需要栈，开销比较小。

法一：

一个栈保存值

一个栈保存最小值

class MinStack { private Deque<Integer> stack; private Deque<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); } public void push(int x) { // 如果是第一次向栈添加元素 if (stack.isEmpty()) { stack.push(x); minStack.push(x); } else { stack.push(x); // 拿出第一个，但是不弹出 int top = minStack.peek(); // 把截止到当前元素的最小值放入 minStack.push(min(top, x)); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int min() { return minStack.peek(); } private int min(int a, int b) { return a < b? a: b; } }

法一优化：

我们把递减的放入即可，不是递减的不放入。

弹出的时候，判断是否和栈数据相同，相同则弹，不同则不弹。

class MinStack { private Deque<Integer> stack; private Deque<Integer> minStack; /** initialize your data structure here. */ public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); } public void push(int x) { // 如果是第一次向栈添加元素 if (stack.isEmpty()) { stack.push(x); minStack.push(x); } else { stack.push(x); // 拿出第一个，但是不弹出 int top = minStack.peek(); // 如果是递减的则放入，否则不放 if (x <= top) { minStack.push(x); } } } public void pop() { int v = stack.pop(); if (minStack.peek() == v) { minStack.pop(); } } public int top() { return stack.peek(); } public int min() { return minStack.peek(); } }

法二：

用一个链表模拟栈。

每次插入按照头插法。

放入的元素是一个结点，结点内部保存着值和最小值和下一个的指针。

说白了，就是把双指针的法一进行了压缩。

class MinStack { private Node head; /** initialize your data structure here. */ public MinStack() { } public void push(int x) { // 头插法 // 得到栈顶的最小值 int topMin = head == null? x: head.min; Node tmp; // 放小的值 if (topMin <= x) { tmp = new Node(x, head, topMin); } else { tmp = new Node(x, head, x); } head = tmp; } public void pop() { Node tmp = head; head = head.next; // 清理掉上一个结点的指针 tmp.next = null; tmp = null; } public int top() { return head.val; } public int min() { return head.min; } } class Node{ public int val; public Node next; public int min; public Node() { } public Node(int val, Node next, int min) { this.val = val; this.next = next; this.min = min; } }