代碼随想錄day3打卡

• 連結清單理論基礎
• 203移除連結清單元素
• 707設計連結清單
• 206反轉連結清單

連結清單理論基礎

203移除連結清單元素

203移除連結清單元素

給你一個連結清單的頭節點 head 和一個整數 val ，請你删除連結清單中所有滿足 Node.val == val 的節點，并傳回 新的頭節點 。

var removeElements = function(head, val) {
    //思路：周遊連結清單，如果目前節點的下一個節點的值等于val，那麼就把目前節點的next指向下下個節點
    if(!head) return null;
    head.next = removeElements(head.next, val);
    return head.val === val ? head.next : head;
};
           

var removeElements = function(head, val) {
    //虛拟頭節點
    //思路：建立一個虛拟頭節點，指向head，然後周遊連結清單，如果目前節點的下一個節點的值等于val，那麼就把目前節點的next指向下下個節點
    let dummyHead = new ListNode(0);
    dummyHead.next = head;
    let cur = dummyHead;
    while(cur.next){
        if(cur.next.val === val){
            cur.next = cur.next.next;
        }else{
            cur = cur.next;
        }
    }
    return dummyHead.next;
}
           

707設計連結清單

707設計連結清單

設計連結清單的實作。您可以選擇使用單連結清單或雙連結清單。單連結清單中的節點應該具有兩個屬性：val 和 next。val 是目前節點的值，next 是指向下一個節點的指針/引用。如果要使用雙向連結清單，則還需要一個屬性 prev 以訓示連結清單中的上一個節點。假設連結清單中的所有節點都是 0-index 的。

在連結清單類中實作這些功能：

get(index)：擷取連結清單中第 index 個節點的值。如果索引無效，則傳回-1。

addAtHead(val)：在連結清單的第一個元素之前添加一個值為 val 的節點。插入後，新節點将成為連結清單的第一個節點。

addAtTail(val)：将值為 val 的節點追加到連結清單的最後一個元素。

addAtIndex(index,val)：在連結清單中的第 index 個節點之前添加值為 val 的節點。如果 index 等于連結清單的長度，則該節點将附加到連結清單的末尾。如果 index 大于連結清單長度，則不會插入節點。如果index小于0，則在頭部插入節點。

deleteAtIndex(index)：如果索引 index 有效，則删除連結清單中的第 index 個節點。

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

    function LinkedList(){
        this.size = 0
        this.head = null
    }

    LinkedList.prototype.getElementAt = function(index){//通過索引找元素
        if(index<0 || index >= this.length) return null
        let cur = this.head
        while(index--){
            cur = cur.next
        }
        return cur
    }

    LinkedList.prototype.find = function(val){
        let cur = this.head
        while(cur){
            if(cur.val === val) return cur
            cur = cur.next
        }
    }

    LinkedList.prototype.addAtTail = function(val){
        const node = ListNode(val)
        this.size++
        if(!this.head){
            this.head = node
        }else{
            let cur = getElementAt(this.size - 1)
            cur.next = node
        }
    }

    LinkedList.prototype.insert = function(index,val){
        if(index<0 || index>=this.size) return false

        let node = new ListNode(val)

        if(index === 0){
            node.next = this.head
            this.head = node
        }else{
            let cur = getElementAt(index-1)
            node.next = cur.next
            cur.next = node
        }
        this.size++
        return true
    }

    LinkedList.prototype.remove = function(index){
        if(index<0 || index>=this.size) return false
        
        let cur = this.head 

        if(index === 0){
            this.head = cur.next
        }else{
            let p = this.getElementAt(index-1)
            cur = p.next
            p.next = cur.next
        }
        this.size--
        return cur.val
    }

    LinkedList.prototype.indexOf = function(val){
        let cur = this.head
        for(let i = 0; i < this.size; i++){
            if(cur.val === val) return i
            cur = cur.next
        }
        return -1
    }

    LinkedList.prototype.remove = function(val){
        let index = this.indexOf(val)
        return this.remove(index)
    }

    LinkedList.prototype.isEmpty = function(){
        return !this.size
    }

           

206反轉連結清單

206反轉連結清單

給你單連結清單的頭節點 head ，請你反轉連結清單，并傳回反轉後的連結清單。

var reverseList = function(head) {
    //思路：周遊連結清單，把目前節點的next指向前一個節點
    let pre = null;
    let cur = head;
    while(cur){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}
           

var reverseList = function(head) {
    //思路：遞歸，把目前節點的next指向前一個節點
    if(!head || !head.next) return head;
    let newHead = reverseList(head.next); //遞歸到最後一個節點，作為新的頭節點
    head.next.next = head;
    head.next = null;
    return newHead;
}