题目描述
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val
和 next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性 prev
以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList
类:
MyLinkedList()
初始化MyLinkedList
对象。int get(int index)
获取链表中下标为index
的节点的值。如果下标无效,则返回-1
。void addAtHead(int val)
将一个值为val
的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)
将一个值为val
的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)
将一个值为val
的节点插入到链表中下标为index
的节点之前。如果index
等于链表的长度,那么该节点会被追加到链表的末尾。如果index
比长度更大,该节点将 不会插入 到链表中。void deleteAtIndex(int index)
如果下标有效,则删除链表中下标为index
的节点。
示例:
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在,链表变为 1->3
myLinkedList.get(1); // 返回 3
提示:
0 <= index, val <= 1000
- 请不要使用内置的 LinkedList 库。
- 调用
get
、addAtHead
、addAtTail
、addAtIndex
和deleteAtIndex
的次数不超过2000
。
分析解答
所以分析都是由易到难,由一般到特殊。
设计节点和链表的类
var LinkedNode = function (val, next) {
this.val = val;
this.next = next;
};
var MyLinkedList = function () {
this.head = null;
this.length = 0;
this.tail = null;
};
getNode
get 方法返回的是 val,不便于我们后续使用,所以在自己写一个 getNode 方便直接获取节点。
MyLinkedList.prototype.getNode = function (index) {
if (index < 0 || index >= this.length) return null;
let cur = this.head;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
};
get
直接调用 getNode 方法。遍历获取 index 处的 LinkedNode。
特殊情况判断:index < 0 || index > this.length
MyLinkedList.prototype.get = function (index) {
if (index < 0 || index >= this.length) return -1;
let result = this.getNode(index);
return result ? result.val : -1;
};
addAtHead
直接使用虚拟头节点的方式插入头节点。
特殊情况处理:插入后也只有一个节点,那么头尾都是 新节点。
MyLinkedList.prototype.addAtHead = function (val) {
let result = new LinkedNode(val, this.head);
this.head = result;
if (!this.tail) {
this.tail = result;
}
this.length++;
};
addAtTail
一般情况,也就是原本就有尾的情况。
特殊情况,处理原本没有尾的情况。
MyLinkedList.prototype.addAtTail = function (val) {
let result = new LinkedNode(val, null);
if (this.tail) {
this.tail.next = result;
this.tail = result;
} else {
this.head = result;
this.tail = result;
}
this.length++;
};
addAtIndex
既然要在 index 处添加 node,那我不先得找到 index 处的 node - this.get(index)
。我要往这里添加 node,但发现前一个 node 连不过来(找不到了),好吧,我先找找前一个node - get(inedx - 1)
。然后就可以顺利连接(插入)了。
特殊情况处理:
index > this.length
- returnindex <= 0
的情况,没想到吧,小于 0 也算哦,都是需要 addAtHead- 添加头部都谈论了,该讨论下添加尾部了,也就是条件
index == this.length
MyLinkedList.prototype.addAtIndex = function (index, val) {
if (index > this.length) return;
if (index <= 0) {
this.addAtHead(val);
return;
}
if (index == this.length) {
this.addAtTail(val);
return;
}
let preNode = this.getNode(index - 1);
let result = new LinkedNode(val, preNode.next);
preNode.next = result;
this.length++;
};
deleteAtIndex
一般情况,获取 index 前一个 node,指向 index 后一个 node 直接删掉。
特殊情况处理:
- index 为 tail 时,tail 改变
index < 0 || index > this.length
- return- index 为 0 时,head 改变
- 同时 index 为 tail 时,tail 改变
MyLinkedList.prototype.deleteAtIndex = function (index) {
if (index < 0 || index >= this.length) return;
if (index == 0) {
this.head = this.head.next;
if (index == this.length - 1) {
this.tail = this.head;
}
this.length--;
return;
}
let preNode = this.getNode(index - 1);
preNode.next = preNode.next.next;
if (index == this.length - 1) {
this.tail = preNode;
}
this.length--;
};
思路拓展
使用虚拟头节点方便操作,不改变原链表,以便在需要时返回头节点或者某个节点。