Day03 | 203.移除链表元素、707.设计链表、206.反转链表 - 《代码随想录算法训练营》

Leetcode 203.移除链表元素
Leetcode 707.设计链表
Leetcode 206.反转链表

Leetcode 203.移除链表元素

题目：203. 移除链表元素

初始思路

很经典的删除链表节点题目。

代码

var removeElements = function (head, val) {
    // 添加一个虚拟头结点 不用考虑删除第一个节点的情况
    const dummyHead = new ListNode(0)
    // 虚拟头结点链接着原来的head节点
    dummyHead.next = head
    // temp是遍历用的指针
    let temp = dummyHead
    while (temp.next !== null) {
        if (temp.next.val == val) {
            // 如果等于这个值就往后链接节点
            temp.next = temp.next.next
        } else {
            // 如果不等于就继续遍历
            temp = temp.next
        }
    }
    // 返回虚拟头结点的下一个节点，就是题目需要的新链表的头结点
    return dummyHead.next
};

感想

删除节点的操作很简单，就是把next节点链接到next.next节点上。
重点是考察虚拟头结点的使用，如果不使用虚拟头结点的话，需要考虑删除的是不是头结点。使用了虚拟头结点之后，把所有节点都看成一样性质的节点，减少了判断。

Leetcode 707.设计链表

题目：707. 设计链表 coderwhy的JavaScript数据结构与算法：https://www.bilibili.com/video/BV1x7411L7Q7 讲解：https://www.bilibili.com/video/BV1FU4y1X7WD

初始思路

之前看coderwhy老师的课的时候手写了一遍单向链表和双向链表，有熟悉的感觉，但是写起来还是很复杂很痛苦！下标很麻烦，而且有一些越界判断。

代码

class Node {
    constructor(val, next) {
        this.val = val
        this.next = next
    }
}
var MyLinkedList = function () {
    this.head = null
    this.tail = null
    this.length = 0
};
/** 
 * @param {number} index
 * @return {number}
 * 获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 */
MyLinkedList.prototype.get = function (index) {
    if (index < 0 || index >= this.length) return -1
    let current = this.head
    let temp = 0
    while (temp++ < index) {
        current = current.next
    }
    return current.val
};
/** 
 * @param {number} val
 * @return {void}
 * 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
 */
MyLinkedList.prototype.addAtHead = function (val) {
    let newNode = new Node(val, this.head)
    this.head = newNode
    this.length++
    if (!this.tail) {
        // 如果尾结点是空，指向新节点
        this.tail = newNode
    }
};
/** 
 * @param {number} val
 * @return {void}
 * 将值为 val 的节点追加到链表的最后一个元素。
 */
MyLinkedList.prototype.addAtTail = function (val) {
    let newNode = new Node(val, null)
    this.length++
    if (this.tail) {
        this.tail.next = newNode
        this.tail = newNode
        return
    }
    this.tail = newNode
    this.head = newNode
};
/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 * 在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
    if (index > this.length) return
    if (index <= 0) {
        this.addAtHead(val)
        return
    }
    if (index == this.length) {
        this.addAtTail(val)
        return
    }
    let temp = 0 // 遍历索引初始化为0
    let current = this.head // 遍历的当前节点初始化为head
    let previous = null // 遍历的上一节点初始化为null
    let newNode = new Node(val, null)
    while (temp++ < index) {
        previous = current
        current = current.next
    }
    // 在当前节点和当前节点的上一节点之间插入新节点，即改变它们的指向
    newNode.next = current
    previous.next = newNode
    this.length++
};
/** 
 * @param {number} index
 * @return {void}
 * 如果索引 index 有效，则删除链表中的第 index 个节点。
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
    // 越界判断
    if (index < 0 || index >= this.length) return
    if (index == 0) {
        // 删除头结点
        this.head = this.head.next
        // 如果删除的这个节点同时是尾结点，也需要处理
        if (index === this.length - 1) {
            this.tail = this.head
        }
    } else {
        let temp = 0
        let current = this.head
        let previous = null
        while (temp++ < index) {
            previous = current
            current = current.next
        }
        // 处理尾结点
        if (index === this.length - 1) {
            this.tail = previous
        } else {
            // 让上一节点的 next 指向当前的节点的 next，相当于删除了当前节点。
            previous.next = current.next
        }
    }
    this.length--
};

感想

写起来真的很痛苦，只能说熟能生巧吧。
写法和代码随想录提供的思路不一样，是按照coderwhy老师的思路写的。
coderwhy老师的课真的讲的不错，可惜没时间看，之后有空把课程补完。

Leetcode 206.反转链表

题目：206. 反转链表

初始思路

暴力解法就是新建一个链表存储反转后的链表，但是浪费空间，之前在原地修改链表即可。

代码

var reverseList = function (head) {
    let current = head
    let previous = null
    // 从前往后遍历
    while (current) {
        // 提前存储next节点
        let next = current.next
        // 让每个节点的next指向前一个节点
        current.next = previous
        // 更新previous位置
        previous = current
        // 更新current位置
        current = next
    }
    return previous
};

感想

没有上一道题复杂。
还是要掌握原地反转链表的方法，指向弯弯绕绕的有点难写写
图示