用 javascript 分类刷 leetcode15. 链表 (图文视频讲解)

var removeNthFromEnd = function (head, n) {    let dummy = new ListNode();    dummy.next = head;    let n1 = dummy;    let n2 = dummy;    for (let i = 0; i <= n; i++) {//n2移动n+1次        n2 = n2.next;    }    while (n2 !== null) {//同时移动n1，n2        n1 = n1.next;        n2 = n2.next;    }    n1.next = n1.next.next;//删除元素    return dummy.next;};

var reverseList = function (head) {  let temp = new ListNode();  let next = null;  while (head) {    next = head.next;//下一个节点    head.next = temp.next;    temp.next = head;//head接在temp的后面    head = next;//head向后移动一位  }  return temp.next;};

var reverseList = function (head) {  let prev = null;  let curr = head;  let next = null;  while (curr !== null) {    next = curr.next;//next向后移动一位    curr.next = prev;//让当前指针curr.next指向前一个指针prev    prev = curr;//prev向后移动一位    curr = next;//curr向后移动一位    //[curr.next, prev, curr] = [prev, curr, curr.next]  }  return prev;};

var reverseList = function(head) {    if (head == null || head.next == null) {//递归终止条件        return head;    }    const newHead = reverseList(head.next);//递归调用reverseList    head.next.next = head;//到了递归最后一层的时候，让后面一个节点指向前一个节点    head.next = null;//前一个节点的next置为空    return newHead;//返回最后一个节点};

var addTwoNumbers = function(l1, l2) {    let head = null, tail = null;    let carry = 0;    while (l1 || l2) {//循环l1,l2链表        const n1 = l1 ? l1.val : 0;        const n2 = l2 ? l2.val : 0;        const sum = n1 + n2 + carry;//两链表节点相加在加进位        if (!head) {            head = tail = new ListNode(sum % 10);//当没有节点的时候新建节点        } else {            tail.next = new ListNode(sum % 10);//有节点的时候则加入tail节点的后面            tail = tail.next;        }        carry = Math.floor(sum / 10);//求进位        if (l1) {//移动l1指针            l1 = l1.next;        }        if (l2) {//移动l2指针            l2 = l2.next;        }    }    if (carry > 0) {//最后一位节点是否有进位        tail.next = new ListNode(carry);    }    return head;};

class ListNode {    constructor(key, value) {//双向链表的单个节点        this.key = key        this.value = value        this.next = null //指向后一个节点        this.prev = null //指向前一个节点    }}
class LRUCache {    constructor(capacity) {        this.capacity = capacity //容量        this.hashTable = {} //存放键值对信息        this.count = 0 //键值对数量        this.dummyHead = new ListNode() //dummy头节点 方便在链表从开始的地方插入        this.dummyTail = new ListNode()    //dummy尾节点 方便在链表从末尾删除        this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互连接        this.dummyTail.prev = this.dummyHead    }
    get(key) {        let node = this.hashTable[key]//查找哈希表中的键值对        if (node == null) return -1 //不存在该键值对 返回-1        this.moveToHead(node) //移动到链表头        return node.value    }
    put(key, value) {        let node = this.hashTable[key] //哈希表中查找该键值对        if (node == null) {            let newNode = new ListNode(key, value) //不存在就创建节点            this.hashTable[key] = newNode //加入哈希表            this.addToHead(newNode) //加入链表头            this.count++ //节点数+1            if (this.count > this.capacity) { //超过容量 从队尾删除一个                this.removeLRUItem()            }        } else {            node.value = value //键值对存在于哈希表中 就更新            this.moveToHead(node) //移动到队头        }    }
    moveToHead(node) {        this.removeFromList(node)//从链表中删除节点        this.addToHead(node)//将该节点添加到链表头    }
    removeFromList(node) {//删除的指针操作        let tempForPrev = node.prev        let tempForNext = node.next        tempForPrev.next = tempForNext        tempForNext.prev = tempForPrev    }
    addToHead(node) {//加入链表头的指针操作        node.prev = this.dummyHead        node.next = this.dummyHead.next        this.dummyHead.next.prev = node        this.dummyHead.next = node    }
    removeLRUItem() {        let tail = this.popTail()//从链表中删除        delete this.hashTable[tail.key]//从哈希表中删除        this.count--    }
    popTail() {        let tailItem = this.dummyTail.prev//通过dummyTail拿到最后一个节点 然后删除        this.removeFromList(tailItem)        return tailItem    }}

var oddEvenList = function(head) {    if (head === null) {        return head;    }    let evenHead = head.next;    let odd = head, even = evenHead;    while (even !== null && even.next !== null) {//偶数指针不为空 继续循环        odd.next = even.next;//奇数指针指向偶数指针的next        odd = odd.next;//移动奇数指针        even.next = odd.next;//偶数指针指向奇数指针的next        even = even.next;//移动偶数指针    }    odd.next = evenHead;//奇数指针结尾连接上偶数指针的开始    return head;};

//例：0->1->2->3  val=2//level1: 0.next = removeElements(1, 2);            return 1                    0->1->3->null//level2: 1.next = removeElements(2, 2);            return 3                    1->3->null//level3: 2.next = removeElements(3, 2);            return 3                    2->3->null//level4: 3.next = removeElements(null, 2);     return null;        3->null
var removeElements = function(head, val) {    if (head === null) {//递归终止 遍历完了链表      return head;    }    head.next = removeElements(head.next, val);//递归调用函数removeElements    return head.val === val ? head.next : head;//如果当前元素值是val，则返回下一个元素，否则直接返回当前元素};

//2->1->2->3//dummy->2->1->2->3var removeElements = function(head, val) {    const dummyHead = new ListNode(0);//创建dummy节点，将dummy节点的next指向head，temp指向dummy    dummyHead.next = head;    let temp = dummyHead;    while (temp.next !== null) {//当temp的next不为null 不断循环节点        if (temp.next.val == val) {            temp.next = temp.next.next;//当temp的next值是要删除的 则删除该节点        } else {            temp = temp.next;//移动temp指针        }    }    return dummyHead.next;};

var deleteNode = function(node) {    node.val = node.next.val//将要删除节点的下一个节点的值覆盖自己的值Ï    node.next = node.next.next//让当前节点指向下一个节点的next};

var swapPairs = function(head) {    if (head === null|| head.next === null) {//终止条件，必须要有两个节点        return head;    }    const newHead = head.next;//反转后链表的头节点，    head.next = swapPairs(newHead.next);//让当前递归层的head.next指向交换后返回的头节点    newHead.next = head;//让反转后的新的头节点指向当前层的head的节点    return newHead;//返回反转后的头节点};

var swapPairs = function(head) {    const dummyHead = new ListNode(0);//虚拟头节点    dummyHead.next = head;//初始的时候让虚拟头节点指向head，    let temp = dummyHead;//temp指针    while (temp.next !== null && temp.next.next !== null) {//循环条件，dummyHead后存在至少两个节点        const node1 = temp.next;//node1指针，即dummyHead后的第一个节点        const node2 = temp.next.next;//node2指针，即dummyHead后的第二个节点        temp.next = node2;//下面三行是两两交换的核心代码        node1.next = node2.next;        node2.next = node1;        temp = node1;//后移一个节点的位置    }    return dummyHead.next;//返回交换后的头节点};

var mergeTwoLists = function(l1, l2) {  //递归终止 分隔到不能分割 也就是两个链表有一个的nxet不存在了 那就没法分割问题了 只能返回    if (l1 === null) {        return l2;    } else if (l2 === null) {        return l1;    } else if (l1.val < l2.val) {//当前节点谁小，就让这个较小的节点的next和另一个链表继续递归合并        l1.next = mergeTwoLists(l1.next, l2);//分隔成合并l1.next, l2的子问题        return l1;    } else {        l2.next = mergeTwoLists(l1, l2.next);        return l2;    }};

var mergeTwoLists = function(l1, l2) {    const prehead = new ListNode(-1);//虚拟头节点
    let prev = prehead;    while (l1 != null && l2 != null) {//循环两个链表        if (l1.val <= l2.val) {//小的节点接在prev的后面            prev.next = l1;            l1 = l1.next;//向后移动l1        } else {            prev.next = l2;//向后移动l2            l2 = l2.next;        }        prev = prev.next;////向后移动prev    }
    prev.next = l1 === null ? l2 : l1;//两个链表一个遍历完，另一个可能还没遍历完，没遍历完的接上
    return prehead.next;//返回prehead.next};

var reverseBetween = function(head, left, right) {    const dummyNode = new ListNode(-1);    dummyNode.next = head;//虚拟头节点
    let pre = dummyNode;    for (let i = 0; i < left - 1; i++) {//pre遍历到left的前一个节点        pre = pre.next;    }
    let rightNode = pre;    for (let i = 0; i < right - left + 1; i++) {//rightNode遍历到right的位置        rightNode = rightNode.next;    }
    let leftNode = pre.next;//保存leftNode    let curr = rightNode.next;//保存rightNode.next
      //切断left到right的子链    pre.next = null;    rightNode.next = null;
        //206题的逻辑 反转left到right的子链    reverseLinkedList(leftNode);
    //返乡连接    pre.next = rightNode;    leftNode.next = curr;    return dummyNode.next;};
const reverseLinkedList = (head) => {    let pre = null;    let cur = head;
    while (cur) {        const next = cur.next;        cur.next = pre;        pre = cur;        cur = next;    }}

var reverseBetween = function(head, left, right) {    const dummy_node = new ListNode(-1);    dummy_node.next = head;//虚拟头节点    let pre = dummy_node;    for (let i = 0; i < left - 1; ++i) {//pre前进到left的前一个节点        pre = pre.next;    }
    let cur = pre.next;    for (let i = 0; i < right - left; ++i) {//循环right - left次 反转中间的节点        const next = cur.next;        cur.next = next.next;        next.next = pre.next;        pre.next = next;    }    return dummy_node.next;//返回虚拟头节点的next};