剑指 Offer 浅刷浅刷

class CQueue {
public:
    stack  headStack;
    stack  rearStack;
    CQueue() {
        
    }
    
    void appendTail(int value) {
        headStack.push(value);
    }
    
    int deleteHead() {
        if (headStack.empty()) {
            return -1;
        } else {
            while (!headStack.empty()) {
                rearStack.push(headStack.top());
                headStack.pop();
            }
            int value = rearStack.top();
            rearStack.pop();
            while (!rearStack.empty()) {
                headStack.push(rearStack.top());
                rearStack.pop();
            }
            return value;
        }
    }
};

使用两个栈实现队列，无非就是一个栈用作队列存储（headStack），另一栈用作队列输出（rearStack），每次要出队的时候就让存储栈（headStack）将所有数据pop到输出栈（rearStack）上，然后输出输出栈的栈顶元素，最后再将剩下的元素pop回存储栈（headStack），每次都如此就完成两个栈实现一个队列了。

class MinStack {
public:
    
    stack  myStack;
    stack  minStack;
    MinStack() {

    }
    
    void push(int x) {
        myStack.push(x);
        if (minStack.empty()) {
            minStack.push(x);
        }
        if (myStack.top() < minStack.top()) {
            minStack.push(x);
        } else if (myStack.size() != minStack.size()) {
            minStack.push(minStack.top());
        }
    }
    
    void pop() {
        if (!myStack.empty()) {
            myStack.pop();
            minStack.pop();
        }
    }
    
    int top() {
        return myStack.top();
    }
    
    int min() {
        return minStack.top();
    }
};

使用两个栈，一个作为普通栈（myStack）另一个作为存储最小数的栈（minStack），这两个栈的size相同，同时push、同时pop，每次向普通栈（myStack）中push数据的时候都与最小栈（minStack）的顶层元素进行比较，若比其小则向最小栈（minStack）中push该元素，否则最小栈（minStack）就将之前顶层数据再进行拷贝一遍push到自己的顶层，这样最小栈（minStack）的顶层元素一直都会是普通栈（myStack）的最小值了。

class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector num;
        stack myStack;
        ListNode *temp = head;
        while (temp) {
            myStack.push(temp->val);
            temp = temp->next;
        }
        while (!myStack.empty()) {
            num.push_back(myStack.top());
            myStack.pop();
        }
        return num;
    }

};

很简单的先用栈存储，然后再pop进vector数组就行了。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *newHead, *rear, *temp;
        newHead = head;
        rear = NULL;
        temp = NULL;
        while (newHead) {
            temp = newHead->next;
            newHead->next = rear;
            rear = newHead;
            newHead = temp;
        }
        return rear;
    }
};

经典的三指针联动，一个指向下一个（temp），一个指向尾（rear），再加个中间操作变量（newHead），使用一个while循环直到链表完了就行。每次让指向下一个的（temp）先跳到下一个，然后再将newHead的next赋值为前一个rear地址，最后newHead跳向temp，rear跳向newHead一直循环就完成了。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == NULL) {
            return head;
        }
        //复制节点
        Node *temp = head;
        while (temp) {
            Node *copyNode = new Node(temp->val);
            copyNode->next = temp->next;
            temp->next = copyNode;
            temp = temp->next->next;
        }
        //完成链表复制节点的随机指针复制
        temp = head;
        while (temp) {
            if (temp->random != NULL) {
                temp->next->random = temp->random->next;
            }
            temp = temp->next->next;
        }
        //将链表一分为二，删除原来的所有节点
        Node *newHead = head->next;
        temp = head->next;
        Node *mid = head;
        while (mid) {
            mid->next = mid->next->next;
            if (temp->next) {
                temp->next = temp->next->next;
                temp = temp->next;
            } else {
                temp->next = NULL;
            }
            mid = mid->next;
        }
        return newHead;
    }
};

• 复制一个新的节点在原有节点之后，如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null
• 从头开始遍历链表，通过 cur.next.random = cur.random.next 可以将复制节点的随机指针串起来，当然需要判断 cur.random 是否存在
• 将复制完的链表一分为二 根据以上信息，我们不难写出代码