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 个节点。

示例 1：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

解题思路

• 通过阅读题目可以发现经常出现以下几点：链表长度、首部、尾部。所以需要在在MyLinkedList中定义以下变量：

var MyLinkedList = function() {
    this._size = 0;//链表长度
    this._head = null;//头部节点
    this._tail = null;//尾部节点
};

getNode(index)

• 该方法用于获取指定下标的节点，属于一个通用函数，后续方法中会重复调用这个函数。

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.getNode = function(index){
    // 判断下表是否合理化
    if(index < 0 || index >= this._size)
        return null;
    // 创建链表
    let cul = new LinkNode(0,this._head);
    // 利用循环找到对应位置的前一个节点，然后用指针指向目标节点
    while(index-- >=0){
        cul = cul.next;
    }
    // 返回目标节点
    return cul;
}

get(index)

• 根据要求：
  • 获取链表中第 index 个节点的值。
  • 如果索引无效，则返回-1。

MyLinkedList.prototype.get = function(index) {
    // 索引无效返回-1
    if(index < 0 || index >= this._size) return -1;
    // 调用getNode方法获得到
    return this.getNode(index).val;
};

addAtHead(val)

• 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• 同样，需要设置一个虚拟头节点进行操作。

/** 
 * @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;
    }
};

addAtTail(val)

• 将值为 val 的节点追加到链表的最后一个元素。

/** 
 * @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;
};

addAtIndex(index,val)

• 在链表中的第 index 个节点之前添加值为 val 的节点。
• 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
• 如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

/** 
 * @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++;
};

deleteAtIndex(index)

• 如果索引 index 有效，则删除链表中的第 index 个节点。

/** 
 * @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 ;
    }
    // 正常情况，获取index节点前一个节点的位置
    const node = this.getNode(index-1);
    // 将前一个节点的next指针指向index节点next指针指向的位置
    node.next = node.next.next;
    // 这里需要将特殊情况index为最后一个节点位置进行处理
    if(index === this._size - 1){
        this._tail = node
    }
    // 链表长度减一
    this._size--;
};