今日学习：

链表理论基础

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

203.移除链表元素

题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

第一想法

这道题考察数据结构链表的基本使用，其实只要加一个虚拟head，然后第一个元素从current.next开始，问题就会轻松很多

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const listnode = new ListNode(0,head)
    //当你将listnode赋值给current时，它们实际上指向相同的内存地址，因此它们引用的是相同的对象
    let current = listnode
    while(current.next){
        if(current.next.val == val){
            current.next = current.next.next;
            //continue的意义为继续判断.例如，1,6,6，6
            continue;
        }
        current = current.next
    }
    //修改current也意味着修改listnode中的数据
    return listnode.next
};

707.设计链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

第一想法

考察链表的基本操作，需要多多回顾

function Node(val) {
    this.val = val
    this.next = null
}

var MyLinkedList = function () {
    this.head = null
    this.length = 0
};

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
    if (index >= this.length || index < 0) return -1
    let current = this.head
    let p = 0
    while (p++ < index) {
        current = current.next
    }
    return current.val
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
    var newNode = new Node(val)
    newNode.next = this.head
    this.head = newNode

    this.length += 1
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
    var newNode = new Node(val)
    var current = this.head
    if (!current) {
        this.head = newNode;
    } else {
        while (current.next) {
            current = current.next
        }
        current.next = newNode
    }
    this.length += 1


};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
    if (index > this.length || index < 0) return false
    var newNode = new Node(val)
    var p = 0
    if (index == 0) {
        newNode.next = this.head
        this.head = newNode
    } else {
        var current = this.head
        var previous = null

        while (p++ < index) {
            previous = current
            current = current.next
        }
        newNode.next = current
        previous.next = newNode
    }

    this.length += 1

};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
    if (index >= this.length || index < 0) return false

    var current = this.head
    if (index == 0) {
        this.head = this.head.next
    } else {
        var p = 0
        var previous = null
        while (p++ < index) {
            previous = current
            current = current.next
        }
        previous.next = current.next
    }

    this.length -= 1
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

206.反转链表

题目链接/文章讲解/视频讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

第一想法

其实一开始想用新的链表来装元素，但看了提示说先看视频，于是有了思路：定义一个current和previous，然后逐一交换指向

206.翻转链表.gif

双指针法：

/**
 * 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) {
    var current = head
    var previous = null
    var temp = null
    while(current){
        temp = current.next
        current.next = previous
        previous = current
        current = temp
    }
    return previous
};

递归法：

var reverse = function(pre, head) {
    if(!head) return pre;
    const temp = head.next;
    head.next = pre;
    pre = head
    return reverse(pre, temp);
}

var reverseList = function(head) {
    return reverse(null, head);
};