代码随想录算法训练营Day3|203 移除链表元素，707 设计

203.移除链表元素

题目描述：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

解题思路

• 如果头节点值等于目标值，需要删除头节点，head = head.next
• 如果存在中间节点值等于目标值，需要删除中间节点，cur.next = cue.next.next

方法一：直接在原链表进行移除操作

注意
1 判断头节点时要用while循环，因为可能存在多个相同节点的值与目标值相等，比如示例三；

var removeElements = function(head, val) {
    // 删除头结点
    while(head && head.val === val) {
        head = head.next
    }
    let cur = head
   // 删除中间节点
    while(cur && cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return head;
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

方法二：利用虚拟头节点

什么是虚拟头节点
在链表头设置一个假的节点dummyHead，该节点存储的数据内容没有实际意义，其指向为真正的头节点。
目的
是由于一般的头节点没有对应的前序，所以需要特殊处理，加入虚拟头节点，可以统一处理逻辑。
如何设置虚拟头节点

// js中
const dummyHead = new ListNode(0, head)

注意
1 返回结果为虚拟头节点的next；

var removeElements = function(head, val) {
    const dummyHead = new ListNode(0, head) // 设置虚拟头节点
    let cur = dummyHead
    while(cur && cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return dummyHead.next;
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

707.设计链表

由于题目比较长，这里请直接看上述链接~

主要实现以下五个方法：

• 获取链表第index个节点的数值
• 在链表的最前面插入一个节点
• 在链表的最后面插入一个节点
• 在链表第index个节点前面插入一个节点
• 删除链表的第index个节点

class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}
var MyLinkedList = function() {
    this._size = 0;// 记录节点个数
    this._head = null; // 存储头节点
    this._tail = null; // 存储尾节点
};
// 定义方法：根据索引返回对应的节点信息
MyLinkedList.prototype.getNode = function(index) {
    if (index < 0 || index >= this._size) {
        return null;
    }
    // 定义虚拟节点
    let cur = new LinkNode(0, this._head);
    while(index >= 0) {
        cur = cur.next;
        index--;
    }
    return cur;
}
/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    if (index < 0 || index >= this._size) {
        return -1;
    }
    return this.getNode(index).val;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let node = new LinkNode(val, this._head);
    // 更新头节点
    this._head = node;
    this._size++;
    // 如果没有尾节点时，更新尾节点
    if (!this._tail) {
        this._tail = node;
    }
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let node = new LinkNode(val, null);
    this._size++;
    // 如果不存在尾节点
    if (!this._tail) {
        this._head = node;
        this._tail = node;
    } else {
        // 先更新当前尾节点的next
        this._tail.next = node;
        // 再更新尾节点为最新节点
        this._tail = node;
    }
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if (index > this._size) {
        return;
    }
    if (index <= 0) {
        this.addAtHead(val);
        return;
    }
    if (index === this._size) {
        this.addAtTail(val);
        return;
    }
    let preNode = this.getNode(index - 1);
    let nextNode = this.getNode(index);
    let node = new LinkNode(val, null);
    preNode.next = node;
    node.next = nextNode;
    this._size++;
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if (index < 0 || index >= this._size) {
        return;
    }
    // 删除头节点
    if (index === 0) {
        this._head = this._head.next;
        //   如果只存在一个节点，那么需要同时更新尾节点
        if (index === (this._size - 1)) {
            this._tail = this._head;
        }
        this._size--;
        return;
    }
    // 获取目标节点的上一个节点
    const node = this.getNode(index - 1);
    node.next = node.next.next;
    if (index === (this._size - 1)) {
        this._tail = node;
    }
    this._size--;
};

206.反转链表

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]

解题思路

• 定义一个pre指针，初始化为null
• 临时变量接收cur.next，并将cur.next 赋值为pre即null，此时当前节点的next已经指向null了
• 重新赋值pre为最新的cur，即数值为头节点，指向为null
• 更新当前节点为下一个节点

var reverseList = function(head) {
    let pre = null;
    let temp;
    let cur = head;
    while(cur) {
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    }
    return pre
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)