栈

后进先出
场景：十进制转二进制、判断字符串的括号是否有效、函数调用栈

栈常用操作：

push
pop
stack[stack.length-1]
20. 有效的括号
``` 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。

```javascript
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
      if(s.length % 2 === 1){ return false; }
    const stack = [];
    const left = ["(", "[", "{"];
    const right = [")", "]", "}"];
    for (let i = 0; i < s.length; i++) {
        if (left.indexOf(s[i]) > -1) {
            stack.push(s[i]);
        } else {
            if (left.indexOf(stack[stack.length - 1]) === right.indexOf(s[i])) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
};

队列

先进先出
栈常用操作：

push
shit
queue[0]
933. 最近的请求次数
```javascript 写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。 int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。保证每次对 ping 的调用都使用比之前更大的 t 值

```javascript
var RecentCounter = function () {
    this.arr = [];
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
    this.arr.push(t);
    while (this.arr[0] < t - 3000) {
        this.arr.shift();
    }
    return this.arr.length;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

链表

元素之间通过 next 连接
常用链表：

修改next
遍历链表1 ```javascript const a = { val :’a’} const b = { val: ‘b’}

a.next = b;

<a name="G86lG"></a>
#### [237. 删除链表中的节点](https://leetcode-cn.com/problems/delete-node-in-a-linked-list/)
```javascript
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head ;
    let p2 = null;
    while(p1){
        const next = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = next;
    }
    return p2;
};

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
    const l3 = new ListNode();
    let p1 = l1;
    let p2 = l2;
    let p3 = l3;
    let c = 0;
    while (p1 || p2) {
        const v1 = p1 ? p1.val : 0;
        const v2 = p2 ? p2.val : 0;
        const val = v1 + v2 + c;
        c = Math.floor(val / 10);
        p3.next = new ListNode(val % 10);

        if (p1) p1 = p1.next;
        if (p2) p2 = p2.next;
        p3 = p3.next
    }
    if (c) p3.next = new ListNode(c);

    return l3.next;
};

83. 删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let p = head;
    while (p && p.next) {
        if (p.val === p.next.val) {
            p.next = p.next.next
        } else {
            p = p.next;
        }
    }
    return head;
};

141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。



进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
    let p1 = head;
    let p2 = head;
    while (p1 && p2 && p2.next) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p1 === p2) {
            return true;
        }
    }
    return false;
};

//思想：龟兔操场跑圈

刷个算法

栈/队列/链表

栈

20. 有效的括号

队列

933. 最近的请求次数

链表

206. 反转链表

2. 两数相加

83. 删除排序链表中的重复元素

141. 环形链表