203.移除鏈表元素

題目描述：

給你一個鏈表的頭節(jié)點 head 和一個整數(shù) val ，請你刪除鏈表中所有滿足 Node.val == val 的節(jié)點，并返回新的頭節(jié)點 。
示例 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
輸出：[]

解題思路

• 如果頭節(jié)點值等于目標值，需要刪除頭節(jié)點，head = head.next
• 如果存在中間節(jié)點值等于目標值，需要刪除中間節(jié)點，cur.next = cue.next.next

方法一：直接在原鏈表進行移除操作

注意
1 判斷頭節(jié)點時要用while循環(huán)，因為可能存在多個相同節(jié)點的值與目標值相等，比如示例三；

var removeElements = function(head, val) {
    // 刪除頭結點
    while(head && head.val === val) {
        head = head.next
    }
    let cur = head
   // 刪除中間節(jié)點
    while(cur && cur.next) {
        if (cur.next.val === val) {
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return head;
};

• 時間復雜度：O(n)
• 空間復雜度：O(1)

方法二：利用虛擬頭節(jié)點

什么是虛擬頭節(jié)點
在鏈表頭設置一個假的節(jié)點dummyHead，該節(jié)點存儲的數(shù)據(jù)內(nèi)容沒有實際意義，其指向為真正的頭節(jié)點。
目的
是由于一般的頭節(jié)點沒有對應的前序，所以需要特殊處理，加入虛擬頭節(jié)點，可以統(tǒng)一處理邏輯。
如何設置虛擬頭節(jié)點

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

注意
1 返回結果為虛擬頭節(jié)點的next；

var removeElements = function(head, val) {
    const dummyHead = new ListNode(0, head) // 設置虛擬頭節(jié)點
    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.設計鏈表

由于題目比較長，這里請直接看上述鏈接~

主要實現(xiàn)以下五個方法：

• 獲取鏈表第index個節(jié)點的數(shù)值
• 在鏈表的最前面插入一個節(jié)點
• 在鏈表的最后面插入一個節(jié)點
• 在鏈表第index個節(jié)點前面插入一個節(jié)點
• 刪除鏈表的第index個節(jié)點

class LinkNode {
    constructor(val, next) {
        this.val = val;
        this.next = next;
    }
}
var MyLinkedList = function() {
    this._size = 0;// 記錄節(jié)點個數(shù)
    this._head = null; // 存儲頭節(jié)點
    this._tail = null; // 存儲尾節(jié)點
};
// 定義方法：根據(jù)索引返回對應的節(jié)點信息
MyLinkedList.prototype.getNode = function(index) {
    if (index < 0 || index >= this._size) {
        return null;
    }
    // 定義虛擬節(jié)點
    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);
    // 更新頭節(jié)點
    this._head = node;
    this._size++;
    // 如果沒有尾節(jié)點時，更新尾節(jié)點
    if (!this._tail) {
        this._tail = node;
    }
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let node = new LinkNode(val, null);
    this._size++;
    // 如果不存在尾節(jié)點
    if (!this._tail) {
        this._head = node;
        this._tail = node;
    } else {
        // 先更新當前尾節(jié)點的next
        this._tail.next = node;
        // 再更新尾節(jié)點為最新節(jié)點
        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;
    }
    // 刪除頭節(jié)點
    if (index === 0) {
        this._head = this._head.next;
        //   如果只存在一個節(jié)點，那么需要同時更新尾節(jié)點
        if (index === (this._size - 1)) {
            this._tail = this._head;
        }
        this._size--;
        return;
    }
    // 獲取目標節(jié)點的上一個節(jié)點
    const node = this.getNode(index - 1);
    node.next = node.next.next;
    if (index === (this._size - 1)) {
        this._tail = node;
    }
    this._size--;
};

206.反轉(zhuǎn)鏈表

題目描述：

給你單鏈表的頭節(jié)點 head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表 。
示例 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，此時當前節(jié)點的next已經(jīng)指向null了
• 重新賦值pre為最新的cur，即數(shù)值為頭節(jié)點，指向為null
• 更新當前節(jié)點為下一個節(jié)點

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)