【leetcode=鏈表】設(shè)計(jì)鏈表
題目：
設(shè)計(jì)鏈表的實(shí)現(xiàn)震檩。您可以選擇使用單鏈表或雙鏈表逛钻。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next哲虾。val 是當(dāng)前節(jié)點(diǎn)的值茶凳，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。如果要使用雙向鏈表令境，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)杠园。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的。
在鏈表類(lèi)中實(shí)現(xiàn)這些功能：
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)混滔。
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //鏈表變?yōu)?-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //現(xiàn)在鏈表是1-> 3
linkedList.get(1); //返回3
提示：
所有val值都在 [1, 1000] 之內(nèi)洒疚。
操作次數(shù)將在 [1, 1000] 之內(nèi)歹颓。
請(qǐng)不要使用內(nèi)置的 LinkedList 庫(kù)。
java代碼：
public class MyLinkedList {
Node first, last;
int size;
/** Initialize your data structure here. */
public MyLinkedList() {
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if (index < 0 || index >= size)
return -1;
else
return node(index).val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
linkFirst(val);
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
linkLast(val);
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
if (index < 0 || index > size)
return;
if (index == size)
linkLast(val);
else
linkBefore(val, node(index));
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
if (index < 0 || index >= size)
return;
unlink(node(index));
}
void linkBefore(int val, Node succ) {
Node pred = succ.prev;
Node newNode = new Node(pred, val, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
}
void linkFirst(int val) {
Node f = first;
Node newNode = new Node(null, val, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}
void linkLast(int val) {
Node l = last;
Node newNode = new Node(l, val, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
}
void unlink(Node x) {
Node prev = x.prev;
Node next = x.next;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
size--;
}
Node node(int index) {
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;
}
}
static class Node {
int val;
Node prev, next;
Node (Node prev, int val, Node next) {
this.val = val;
this.prev = prev;
this.next = next;
}
}
}
