leetcode707-设计链表

devtools/2025/1/20 3:21:48/

思路

本题也是用了虚拟头节点来进行解答，这样的好处是，不管是头节点还是中间的节点都可以当成是中间节点来处理，用同一套方法就可以进行处理，而不用考虑太多的边界条件。
下面题目中最主要的实现就是添加操作addAtIndex和删除操作deleteAtIndex，对于在头节点和尾节点添加其实都是调用添加方法就可以，头节点设置index = 0, 尾节点设置index = size

get

获取某个节点值，通过循环遍历到当前节点，设置一个cur来记录每次遍历到的当前节点，然后返回cur.val

add

我们要添加的时候一定需要找到的是索引的前一个节点，因为这样才可以进行添加，如果找成了后一个节点，那么我们由于这里设置的是单向链表，就无法再去索引到前一个节点，也就没办法进行连接，找到了前一个节点之后，需要先把要添加到节点设置为cur.next，然后再设置cur.next = node; ，注意这里顺序一定不能错，一旦先把cur.next 设置为node以后，原先的cur.next就断掉，node.next就无法继续设置

delete

这里删除操作可以参考前一篇的博文：移除链表元素
不过这里的删除操作会更简单一些，总的来说就是跳过需要删除的节点，把cur.next 设置为cur.next.next

实现

// 创建链表节点
class CreateNode{constructor(val,next){this.val = val ?? 0;this.next = next ?? null;}
}var MyLinkedList = function() {this.size = 0;this.dummy = new CreateNode(0);
};/** 
获取下标为index的值* @param {number} index* @return {number}*/
MyLinkedList.prototype.get = function(index) {if(index < 0 || index >= this.size) return -1;let cur = this.dummy.next;for(let i = 0; i < index;i++){cur = cur.next}return cur.val;
};/** 
添加到头节点* @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtHead = function(val) {this.addAtIndex(0,val);
};/** 
添加到尾节点* @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtTail = function(val) {this.addAtIndex(this.size,val);
};/** 
添加到index节点前* @param {number} index * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtIndex = function(index, val) {if(index < 0 || index > this.size) return;// 可以进行添加，size++this.size++;let cur = this.dummy;for(let i = 0;i<index;i++){cur = cur.next;}// 进行添加操作const node = new CreateNode(val);node.next = cur.next;cur.next = node;
};/** 
删除节点* @param {number} index* @return {void}*/
MyLinkedList.prototype.deleteAtIndex = function(index) {if(index >= this.size || index < 0) return;// 可以进行删除，长度size-1this.size--// 获取到可删除的节点的前一个节点let cur = this.dummy;for(let i = 0;i<index;i++){cur=cur.next;}// 删除操作cur.next = cur.next.next
};