代码随想录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;
}