707.设计链表
解题思路
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
出现的问题
其实上课都学过，用图来说都记得都会。但是不知道代码语言该如何去操作。
JavaScript解法代码
class LinkNode{
constructor(value,next){
this.val = value
this.next = next
}
}
var MyLinkedList = function() {
this._size = 0
//认为是头结点
this._head = null
this._tail = null
};
/**
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.getNode = function(index) {
// 判断index的合法性
if(index < 0 || index >= this._size) return null;
// 创建虚拟头节点
let current = new LinkNode(0,this._head)
// while 遍历之后的节点
while(index >= 0){
current = current.next
index--
}
return current
};
MyLinkedList.prototype.get = function(index) {
// 判断index的合法性
if(index < 0 || index >= this._size) return -1
return this.getNode(index).val
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
// 初始化这个新节点，并且首先将new node的next指向head节点
const newNode = new LinkNode(val,this._head)
// 然后将虚拟头节点指向这个新节点。代码这么写↓
this._head = newNode
this._size++
if(!this._tail) {
this._tail = newNode;
}
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
// 初始化新节点，并将新节点的next指向null
const newNode = new LinkNode(val, null)
this._size++
if(this._tail){
this._tail.next = newNode
this._tail = newNode
return
}
// 应该是什么特殊边界情况
this._tail = newNode;
this._head = newNode;
};
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtIndex = function(index, val) {
// 判断index的合法性
// if(index < 0 || index >= this._size) return null
if(index > this._size) return;
if(index <= 0) {
this.addAtHead(val);
return;
}
if(index === this._size) {
this.addAtTail(val);
return;
}
// 获取插入第index节点的上一个节点
const previousNode = this.getNode(index - 1);
// 该插入节点指向原本的下一个阶段，然后上一个节点指向该插入节点
previousNode.next = new LinkNode(val, previousNode.next);
this._size++;
};
/**
* @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 previousNode = this.getNode(index - 1);
// 直接指向下一个节点的下一个节点
previousNode.next = previousNode.next.next
// 处理尾节点
if(index === this._size - 1) {
this._tail = node;
}
this._size--
};
/**
* 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)
*/
总结：
增加节点，重点是先将新节点的next指向下一个节点，再将前一个节点的next指向这个节点。
