链表 栈 队列的补充内容

二点五章：链表，栈，队列，堆的补充内容

本文主要是对第一节课和第二节课部分没有讲到的部分进行补充 第一节课：[[第一章：链表]] 第二节课：[[第二章：栈 队列 堆]]

链表逆序拆解详解

已知链表头节点指针head，将链表逆序，不可申请额外空间 后面都是一样的

链表逆序——头插法

设置一个临时指针temp_head ，利用head遍历指针，每次遍历一个节点即将该节点插入到temp_head后面 头插法原理实现

struct ListNode* reverseList(struct ListNode* head){

    struct ListNode temp_head = {0};//临时节点

    while(head){

        struct ListNode* next = head->next ;//对head->进行备份

        head->next = temp_head.next;  //把head接在临时头节点和后面之间

        temp_head.next = head;//连接temp_head 和对应节点

        head = next;//head指向下一个节点

    }

    return temp_head.next;

  

}

实际上头插法和[[第一章：链表#链表逆序|就地逆置法]] 在计算机里面并没有本质上的不同 ，就地逆置法也是只用指针，头插法里面的临时节点用到的部分也仅仅是temp_head的指针域

快慢指针求环条件分析

本题是对[[第一章：链表#链表求环#方法2|Linked List Cycle II method2]] 的优化 本题的代码

struct ListNode *detectCycle(struct ListNode *head) {

    struct ListNode* fast = head ;

    struct ListNode* slow = head;//快慢指针

    struct ListNode * meet  = NULL; //相遇的指针，初始化为空

    while(fast){//链表无环，且节点个数为奇数个，这里返回

        slow = slow->next;//slow 和fast都先各走一部

        fast = fast->next;

        if(!fast)//链表无环，节点个数为偶数个，这里返回

        {

            return NULL;

        }

        fast = fast->next;//快指针再走一步

        if(fast == slow)

        {

            meet = slow;//把相遇的meet指针定义到slow或者fast上

            break;

        }

    }

    if(meet == NULL){

        return NULL;

  

    }

    while(head&&meet){

        if(head == meet){//如果两个指针相遇

            return head;

  

        }

        head=head->next;

        meet = meet->next;

    }

    return NULL;

}

在这一段代码里

    if(meet == NULL){

        return NULL;
    }

这句代码实际上是不需要的 如果meet == NULL的话

   while(head&&meet){

        if(head == meet){//如果两个指针相遇

            return head;

  

        }

        head=head->next;

        meet = meet->next;

    }

根本不会进入这一段循环，相当已经判断了，所以不需要额外判断一次并return NULL;

while(fast)用来判断偶节点是为空 if(!fast) 用来判断奇节点为空

使用栈实现队列（方法2 双栈法）

本文是[[第二章：栈 队列 堆#用栈实现队列|使用栈实现队列]] 的第二个方法 之前的办法的整体复杂度是O($n^2$) 平均复杂度是O($n$) 现在的办法是整体复杂度O($n$),平均复杂度是O(1)

本方法的解决办法

class MyQueue {

public:

    MyQueue() {

  

    }

    void push(int x) {

        _input.push(x);//将xpush进input

    }

    int pop() {

        adjust();//调整在进行pop

        int x = _output.top();

        _output.pop();

        return x;

    }

    int peek() {

        adjust();//调整，并返回output.top()

        return _output.top();

    }

    bool empty() {//input和output都为真

        return _output.empty()&&_input.empty();

    }

private:

    void adjust(void){

        if(!_output.empty()){//output不为真的时候不需要调整

            return;

        }

        while(!_input.empty()){//调整过程

            _output.push(_input.top());//input每一个元素都push进入output里面

            _input.pop();//弹出input

        }

    }

    std::stack<int> _input;

    std::stack<int>_output;

};