• 算法|203. 移除链表元素 206.反转链表 707. 设计链表


    链表

    关于链表这块还是不太熟悉, 形似数组,却和数组不一样

    203. 移除链表元素

    while一直循环当前, 循环模块改变cur到下一个

    /**
     * @param {ListNode} head
     * @param {number} val
     * @return {ListNode}
     */
    var removeElements = function (head, val) {
      const ret = new ListNode(0, head);
      let cur = ret;
      while (cur.next) {
        if (cur.next.val === val) {
          cur.next = cur.next.next;
          // 继续下一个循环
          continue;
        }
        cur = cur.next;
      }
      return ret.next;
    };
    console.log(removeElements([7, 7, 7, 7], 7));
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    206.反转链表

    这个还算好理解,建几个临时变量, 改变pre cur next的值

    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var reverseList = function (head) {
      let temp = null;
      let pre = null;
      let cur = head;
      while (cur) {
        // 下一个存储起来
        temp = cur.next;
        // 当前值的next指向 pre
        cur.next = pre;
        // 将当前值给pre
        pre = cur;
        // 改变当前值为下一个,继续循环
        cur = temp;
      }
      return pre;
    };
    
    console.log(reverseList([1, 2, 3, 4, 5]));
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    707. 设计链表

    内容较多, 后续补上

    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
    • 135
  • 相关阅读:
    公司要做大数据可视化看板,除了EXCEL以外有没有好用的软件可以用
    Flutter CustomScrollView 的使用 及 常用的Sliver系列组件
    AAAI 22: Orthogonal Graph Neural Networks
    JVM与JMM的关系
    2022年在uniapp中引入vant Weapp
    [Kotlin Tutorials 22] 协程中的异常处理
    【Vue篇】Vue 项目下载、介绍(详细版)
    redis--springboot使用redis
    CVE-2022-26134 Confluence OGNL表达式注入命令执行漏洞复现
    web前端课程设计——动漫网页2个网页HTML+CSS web前端开发技术 web课程设计 网页规划与设计
  • 原文地址:https://blog.csdn.net/shjavadown/article/details/136261309