剑指offer专题

剑指 Offer 09. 用两个栈实现队列

class CQueue {
    LinkedList<Integer> A, B; 
    public CQueue() {
        A = new LinkedList<Integer> ();
        B = new LinkedList<Integer> ();
    }
    
    public void appendTail(int value) {
        A.addLast(value);
    }
    
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty()){
            B.addLast(A.removeLast());
        }
        return B.removeLast();
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

剑指 Offer 30. 包含min函数的栈

class MinStack {
    Stack<Integer> A, B;
    /** initialize your data structure here. */
    public MinStack() {
        A = new Stack<> ();
        B = new Stack<> ();
    }
    
    public void push(int x) {
        A.push(x);
        if(B.empty() || x <= B.peek()){
            B.push(x);
        }else{
            B.push(B.peek());
        }
    }
    
    public void pop() {
        A.pop();
        B.pop();
    }
    
    public int top() {
        return A.peek();
    }
    
    public int min() {
        return B.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<>();
        while(head != null){
            stack.addLast(head.val);
            head = head.next;
        }
        int[] result = new int[stack.size()];
        for(int i = 0; i < result.length; i++){
            result[i] = stack.removeLast();
        }
        return result;
    }
}

剑指 Offer 24. 反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null){
          	// temp存下一步 -> 下一步存前一步 -> 前一步存当前 -> 当前走temp
            ListNode temp = cur.next;
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = temp;               // cur 访问下一节点
        }
        return pre;
    }
}