707.设计链表
难度：中等
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：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。
解题思路
这道题目设计链表的五个接口：
- 获取链表第 index 个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第 index 个节点前面插入一个节点
- 删除链表的第 index 个节点
可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题
结合第 203 题，为了操作上的统一，这里我们选择给链表加上 虚拟头节点，会更方便一些。
我的代码（单链表）
java
//单链表
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
this.next = null;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head;
//初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
public int get(int index) {
//如果index超出当前链表范围，返回-1
if (index < 0 || index >= size) {
return -1;
}
//注意这里的head是虚拟头节点
ListNode currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
return currentNode.val;
}
//在链表最前面插入一个节点，等价于在第0个元素前添加
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
//注意这里的head是虚拟头节点
ListNode currentNode = head;
ListNode pre = null;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
pre = currentNode;
currentNode = currentNode.next;
}
pre.next = new ListNode(val, currentNode);
//链表大小更新
size++;
}
//删除第index个节点
public void deleteAtIndex(int index) {
//如果index超出当前链表范围，返回-1
if (index < 0 || index >= size) {
return;
}
//注意这里的head是虚拟头节点
ListNode currentNode = head;
ListNode pre = null;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
pre = currentNode;
currentNode = currentNode.next;
}
pre.next = currentNode.next;
//链表大小更新
size--;
}
}时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
空间复杂度: O(n)
我的代码（双链表）
java
class ListNode {
int val;
ListNode pre;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
this.pre = null;
this.next = null;
}
ListNode(int val, ListNode pre, ListNode next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}
class MyLinkedList {
//size存储链表元素的个数
int size;
//虚拟头结点
ListNode head;
//虚拟尾节点
ListNode tail;
//初始化链表
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
//这一步非常关键，否则在加入头结点的操作中会出现 null.next 的错误！！！
head.next = tail;
tail.pre = head;
}
//获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
public int get(int index) {
//如果index超出当前链表范围，返回-1
if (index < 0 || index >= size) {
return -1;
}
ListNode currentNode = null;
//判断是哪一边遍历时间更短
if (index >= size / 2) { //从tail开始
//注意这里的tail是虚拟尾节点
currentNode = tail;
for (int i = size; i > index; i--) {
currentNode = currentNode.pre;
}
} else if (index < size / 2) { //从head开始
//注意这里的head是虚拟头节点
currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
}
}
return currentNode.val;
}
//在链表最前面插入一个节点，等价于在第0个元素前添加
public void addAtHead(int val) {
addAtIndex(0, val);
}
//在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
public void addAtTail(int val) {
addAtIndex(size, val);
}
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
ListNode currentNode = null;
ListNode pre = null;
//从head开始
currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
pre = currentNode.pre;
}
ListNode temp = new ListNode(val, pre, currentNode);
pre.next = temp;
currentNode.pre = temp;
//链表大小更新
size++;
}
//删除第index个节点
public void deleteAtIndex(int index) {
//如果index超出当前链表范围，返回-1
if (index < 0 || index >= size) {
return;
}
//注意这里的head是虚拟头节点
ListNode currentNode = null;
ListNode pre = null;
ListNode next = null;
//判断是哪一边遍历时间更短
if (index >= size / 2) { //从tail开始
currentNode = tail;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = size; i > index; i--) {
currentNode = currentNode.pre;
pre = currentNode.pre;
next = currentNode.next;
}
} else if (index < size / 2) {//从head开始
currentNode = head;
//包含一个虚拟头节点，所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
currentNode = currentNode.next;
pre = currentNode.pre;
next = currentNode.next;
}
}
pre.next = next;
next.pre = pre;
//链表大小更新
size--;
}
}时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
空间复杂度: O(n)
总结
如果使用 C，C++ 编程语言的话，不要忘了还要从内存中删除这两个移除的节点。
当然如果使用 Java ，Python 的话就不用手动管理内存了。
注意虚拟头节点的引入，可以使代码逻辑更统一。