707.設(shè)計(jì)鏈表
解題思路
- get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值诞帐。如果索引無(wú)效蟋滴，則返回-1。
- addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)陨囊。插入后肛著，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)煌恢。
- addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素归形。
- addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長(zhǎng)度葵孤，則該節(jié)點(diǎn)將附加到鏈表的末尾担钮。如果 index 大于鏈表長(zhǎng)度，則不會(huì)插入節(jié)點(diǎn)尤仍。如果index小于0箫津，則在頭部插入節(jié)點(diǎn)。
- deleteAtIndex(index)：如果索引 index 有效宰啦，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)鲤嫡。
出現(xiàn)的問(wèn)題
其實(shí)上課都學(xué)過(guò)，用圖來(lái)說(shuō)都記得都會(huì)绑莺。但是不知道代碼語(yǔ)言該如何去操作。
JavaScript解法代碼
class LinkNode{
constructor(value,next){
this.val = value
this.next = next
}
}
var MyLinkedList = function() {
this._size = 0
//認(rèn)為是頭結(jié)點(diǎn)
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;
// 創(chuàng)建虛擬頭節(jié)點(diǎn)
let current = new LinkNode(0,this._head)
// while 遍歷之后的節(jié)點(diǎn)
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) {
// 初始化這個(gè)新節(jié)點(diǎn)惕耕，并且首先將new node的next指向head節(jié)點(diǎn)
const newNode = new LinkNode(val,this._head)
// 然后將虛擬頭節(jié)點(diǎn)指向這個(gè)新節(jié)點(diǎn)纺裁。代碼這么寫(xiě)↓
this._head = newNode
this._size++
if(!this._tail) {
this._tail = newNode;
}
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
// 初始化新節(jié)點(diǎn)，并將新節(jié)點(diǎn)的next指向null
const newNode = new LinkNode(val, null)
this._size++
if(this._tail){
this._tail.next = newNode
this._tail = newNode
return
}
// 應(yīng)該是什么特殊邊界情況
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節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
const previousNode = this.getNode(index - 1);
// 該插入節(jié)點(diǎn)指向原本的下一個(gè)階段，然后上一個(gè)節(jié)點(diǎn)指向該插入節(jié)點(diǎn)
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;
// 如果刪除的這個(gè)節(jié)點(diǎn)同時(shí)是尾節(jié)點(diǎn)欺缘，要處理尾節(jié)點(diǎn)
if(index === this._size - 1){
this._tail = this._head
}
this._size--;
return;
}
// 獲取要?jiǎng)h除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
const previousNode = this.getNode(index - 1);
// 直接指向下一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
previousNode.next = previousNode.next.next
// 處理尾節(jié)點(diǎn)
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)
*/
總結(jié)：
增加節(jié)點(diǎn)栋豫，重點(diǎn)是先將新節(jié)點(diǎn)的next指向下一個(gè)節(jié)點(diǎn)，再將前一個(gè)節(jié)點(diǎn)的next指向這個(gè)節(jié)點(diǎn)谚殊。
