• 代码随想录算法训练营第三天| 203.移除链表元素、707.设计链表 、206.反转链表(JS写法)


    203 移除链表元素

    题目链接/文章讲解/视频讲解::https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
    方法一:设置虚拟头节点

    /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var removeElements = function(head, val) {
        let dummyHead = new ListNode();
        dummyHead.next = head;
        let cur = dummyHead;
        while(cur !== null && cur.next !== null){
            if(cur.next.val === val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }       
        }
        return dummyHead.next;
    
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    注意:
    1.while循环的条件不能只写cur.next !== null,必须加上cur !==null
    2.返回的是dummyHead.next,而不是dummyHead
    3.cur=cur.next要写在else里面,而不是单独写
    方法二:不设置头节点,需要单独考虑头节点是要删除的节点这一情况

    /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var removeElements = function(head, val) {
        //不设置虚拟头节点
        //需要单独考虑如果要删除的点是头节点这一情况
        while(head !== null && head.val == val){
            head = head.next;
        }
        let cur = head;
        while(cur !== null && cur.next !== null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    206 反转链表

    题目链接/文章讲解/视频讲解:https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html
    方法一:迭代法
    在这里插入图片描述

    /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function(head) {
        //需要创建两个指针
        //pre首先等于null,尾随cur
        let pre = null;
        //推进指针
        let cur = head;
        //cur指向null时,退出循环
        while(cur !== null){
            let temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //返回的是pre,因为当前cur已经指向null
        return pre;
    
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    方法二:尾递归

    /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function(head) {
        function letCurPointToPre(pre,cur){
            //cur等于null时,递归结束,返回pre
            if(cur === null) return pre;
            let next = cur.next;
            cur.next = pre;
            //尾递归,相当于pre=cur,cur=next
            return letCurPointToPre(cur,next);
        }
        //prev,cur的初始值分别为null,head
        return letCurPointToPre(null,head);
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    707 设计链表

    题目链接/文章讲解/视频讲解:https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

    class LinkNode {
        constructor(val, next) {
            this.val = val;
            this.next = next;
        }
    }
    
    /**
     * Initialize your data structure here.
     * 单链表 储存头尾节点 和 节点数量
     */
    var MyLinkedList = function() {
        this._size = 0;
        this._tail = null;
        this._head = null;
    };
    
    /**
     * Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
     * @param {number} index
     * @return {number}
     */
    MyLinkedList.prototype.getNode = function(index) {
        if(index < 0 || index >= this._size) return null;
        // 创建虚拟头节点
        let cur = new LinkNode(0, this._head);
        // 0 -> head
        while(index-- >= 0) {
            cur = cur.next;
        }
        return cur;
    };
    MyLinkedList.prototype.get = function(index) {
        if(index < 0 || index >= this._size) return -1;
        // 获取当前节点
        return this.getNode(index).val;
    };
    
    /**
     * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. 
     * @param {number} val
     * @return {void}
     */
    MyLinkedList.prototype.addAtHead = function(val) {
        const node = new LinkNode(val, this._head);
        this._head = node;
        this._size++;
        if(!this._tail) {
            this._tail = node;
        }
    };
    
    /**
     * Append a node of value val to the last element of the linked list. 
     * @param {number} val
     * @return {void}
     */
    MyLinkedList.prototype.addAtTail = function(val) {
        const node = new LinkNode(val, null);
        this._size++;
        if(this._tail) {
            this._tail.next = node;
            this._tail = node;
            return;
        }
        this._tail = node;
        this._head = node;
    };
    
    /**
     * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. 
     * @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;
        }
        // 获取目标节点的上一个的节点
        const node = this.getNode(index - 1);
        node.next = new LinkNode(val, node.next);
        this._size++;
    };
    
    /**
     * Delete the index-th node in the linked list, if the index is valid. 
     * @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--;
    };
    
    // MyLinkedList.prototype.out = function() {
    //     let cur = this._head;
    //     const res = [];
    //     while(cur) {
    //         res.push(cur.val);
    //         cur = cur.next;
    //     }
    // };
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * var obj = new MyLinkedList()
     * var param_1 = obj.get(index)
     * obj.addAtHead(val)
     * obj.addAtTail(val)
     * obj.addAtIndex(index,val)
     * obj.deleteAtIndex(index)
     */
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134

    这道题真的太难了呜呜呜呜呜呜,第二次做依然做得难受/(ㄒoㄒ)/~~

  • 相关阅读:
    智云通CRM:读懂客户的五种“成交信号”,恰到好处地收单?
    《MySQL实战45讲》——学习笔记17 “随机排序、内存临时表“
    驾校在线考试系统源码 手机+PC+平板自适应
    内存取证系列3
    JS-获取DOM元素的五种方法
    卷积神经网络信号处理,卷积神经网络应用领域
    Ubuntu系统之管理文件权限一
    217页企业大数据能力平台建设技术方案
    JavaScript设计模式之责任链模式
    31年前的Beyond演唱会,是如何超清修复的?
  • 原文地址:https://blog.csdn.net/weixin_44776979/article/details/136248196