• 代码随想录算法训练营第三天| 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ㄒ)/~~

  • 相关阅读:
    三分钟了解JVM的垃圾回收和三色标记
    Java电子病历编辑器项目源码 采用B/S(Browser/Server)架构
    遇到问题[已解决]TypeError: ‘odict_keys‘ object is not subscriptable
    mac 脚本实现APP启动与关闭
    Educational Codeforces Round 129 F. Unique Occurrences(树上问题)
    Codeforces Round #803 (Div. 2) A. XOR Mixup
    Git之路
    问题解决:ModuleNotFoundError: No module named ‘skimage‘
    E. Red-Black Pepper
    关于 爷爷组件传值给爸爸组件 孙子组件又直接把值传给爸爸组件 (个人笔记记录) 外人看不懂就不要看
  • 原文地址:https://blog.csdn.net/weixin_44776979/article/details/136248196