一、题目

二、题解

// 定义节点类，每个节点都有一个值和一个指向下一个节点的引用
class LinkNode{
    constructor(val,next){ // 构造函数，接收节点值和下一个节点的引用
        this.val=val       // 节点的值
        this.next=next     // 指向下一个节点的引用
    }
}

// 定义链表类
var MyLinkedList = function() {
    this.size=0            // 链表的大小（节点数量）
    this.head=null         // 链表的头节点
    this.tail=null         // 链表的尾节点
};

// 获取链表中第index个节点的值
MyLinkedList.prototype.get = function(index) {
     if(index < 0 || index >= this.size) return -1; // 如果索引无效，返回-1
    // 获取当前节点并返回其值
    return this.getNode(index).val;
};

// 在链表头部添加一个节点
MyLinkedList.prototype.addAtHead = function(val) {
    const node = new LinkNode(val, this.head); // 创建新节点，其下一个节点是当前的头节点
    this.head = node;                           // 更新头节点为新节点
    this.size++;                                // 链表大小加1
    if(!this.tail) {                            // 如果链表为空，则新节点也是尾节点
        this.tail = node;
    }
};

// 在链表尾部添加一个节点
MyLinkedList.prototype.addAtTail = function(val) {
     const node = new LinkNode(val, null);      // 创建新节点，下一个节点为null
    this.size++;                                // 链表大小加1
    if(this.tail) {                             // 如果链表不为空
        this.tail.next = node;                  // 当前尾节点的下一个节点是新节点
        this.tail = node;                       // 更新尾节点为新节点
        return;                                 // 结束函数执行
    }
    this.tail = node;                           // 如果链表为空，则新节点既是头节点也是尾节点
    this.head = node;
};

// 获取链表中第index个节点
MyLinkedList.prototype.getNode = function(index) {
    if(index < 0 || index >= this.size) return null; // 如果索引无效，返回null
    // 创建虚拟头节点，其下一个节点是实际的头节点
    let cur = new LinkNode(0, this.head);
    // 移动到第index个节点
    while(index-- >= 0) {
        cur = cur.next;
    }
    return cur; // 返回目标节点
};

// 在链表中的第index个位置添加一个节点
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index>this.size) return;                   // 如果索引超出链表大小，不执行任何操作
    if(index===this.size){                        // 如果索引等于链表大小，在尾部添加节点
        this.addAtTail(val)
        return;
    }
    if(index<=0){                                 // 如果索引小于等于0，在头部添加节点
        this.addAtHead(val)
        return;
    }
    const node = this.getNode(index-1)            // 获取第index-1个节点
    node.next=new LinkNode(val,node.next)         // 在其后面添加新节点
    this.size++;                                  // 链表大小加1
};

// 删除链表中第index个位置的节点
MyLinkedList.prototype.deleteAtIndex = function(index) {
     if(index < 0 || index >= this.size) return; // 如果索引无效，不执行任何操作
    if(index === 0) {                             // 如果是删除头节点
        this.head = this.head.next;               // 更新头节点为下一个节点
        // 如果删除的这个节点同时是尾节点，更新尾节点为null
        if(index === this.size - 1){
            this.tail = this.head
        }
        this.size--;                              // 链表大小减1
        return;                                   // 结束函数执行
    }
    // 获取目标节点的上一个节点
    const node = this.getNode(index - 1);        
    node.next = node.next.next;                   // 跳过要删除的节点，即删除操作
    // 如果删除的是尾节点，更新尾节点
    if(index === this.size - 1) {
        this.tail = node;
    }
    this.size--;                                  // 链表大小减1
};