一、题目
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index) ：获取链表中第
index个节点的值。如果索引无效，则返回-1。 addAtHead(val) ：在链表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。 addAtTail(val) ：将值为val的节点追加到链表的最后一个元素。 addAtIndex(index,val) ：在链表中的第index个节点之前添加值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 deleteAtIndex(index) ：如果索引index有效，则删除链表中的第index个节点。
二、示例
2.1> 示例：
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1-> 3 linkedList.get(1); //返回3
提示：
- • 所有
val值都在[1, 1000]之内。 - • 操作次数将在
[1, 1000]之内。 - • 请不要使用内置的 LinkedList 库。
三、解题思路
其实这类题就是让我们自己去实现容器，跟设计HashSet、设计HashMap、设计Deque等等是一类题。对于Java实现来说，我们只需要参照LinkedList即可。
当然，在JDK中LinkedList是采用双向链表实现的底层逻辑。此处与单向链表实现区别不大。
这道题就不画图了，具体代码请参照——代码实现。
四、代码实现
代码语言：javascript复制class MyLinkedList {
private Node first = null;
private Node last = null;
private int size = 0;
public MyLinkedList() {
}
public int get(int index) {
if (!isElementIndex(index)) return -1;
return getNode(index).val;
}
public void addAtHead(int val) {
Node newNode = new Node(null, val, first);
if (first != null) first.prev = newNode;
first = newNode;
if (last == null) last = first;
size ;
}
public void addAtTail(int val) {
Node newNode = new Node(last, val, null);
if (last != null) last.next = newNode;
last = newNode;
if (first == null) first = last;
size ;
}
public void addAtIndex(int index, int val) {
if (index > size) return;
if (index == size) {
addAtTail(val);
} else if (index <= 0) {
addAtHead(val);
} else {
Node node = getNode(index);
Node newNode = new Node(node.prev, val, node);
if (node.prev != null) node.prev.next = newNode;
node.prev = newNode;
size ;
}
}
public void deleteAtIndex(int index) {
if (!isElementIndex(index)) return;
Node node = getNode(index);
if (index == 0) {
first = node.next;
if (size > 1) node.next.prev = null;
node.next = null;
} else if (index == size - 1) {
last = node.prev;
if (size > 1) node.prev.next = null;
node.prev = null;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
size--;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
public Node getNode(int index) {
if (!isElementIndex(index)) return null;
if (index < (size >> 1)) {
Node x = first;
for (int i = 0; i < index; i )
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
private static class Node {
int val;
Node next, prev;
Node(Node prev, int val, Node next) {
this.val = val;
this.next = next;
this.prev = prev;
}
}
}
