題目
設(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 的。
在鏈表類中實(shí)現(xiàn)這些功能：
get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值签杈。如果索引無效瘫镇，則返回-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 等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾睁壁。如果 index 大于鏈表長度背苦，則不會插入節(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)。
請不要使用內(nèi)置的 LinkedList 庫遂填。
題解
使用單鏈表
class MyLinkedList {
int size;
ListNode head;
/** Initialize your data structure here. */
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
/** 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;
ListNode curr = head;
for(int i=0;i<index+1;i++) curr = curr.next;
return curr.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) {
addAtIndex(0,val);
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
addAtIndex(size,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>size) return;
if(index<0) index=0;
++size;
ListNode pred = head;
for(int i=0;i<index;i++) pred = pred.next;
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
/** 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;
size--;
ListNode pred = head;
for(int i=0;i<index;i++) pred = pred.next;
pred.next = pred.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
復(fù)雜度分析
時(shí)間復(fù)雜度：
- addAtHead： \mathcal{O}(1)O(1)
- addAtInder铲觉，get，deleteAtIndex: \mathcal{O}(k)O(k)吓坚，其中 kk 指的是元素的索引撵幽。
- addAtTail：\mathcal{O}(N)O(N)，其中 NN 指的是鏈表的元素個(gè)數(shù)礁击。
空間復(fù)雜度：所有的操作都是 O(1)O(1)盐杂。
使用雙鏈表
public class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode(int x) { val = x; }
}
class MyLinkedList {
int size;
// sentinel nodes as pseudo-head and pseudo-tail
ListNode head, tail;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
/** 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 is invalid
if (index < 0 || index >= size) return -1;
// choose the fastest way: to move from the head
// or to move from the tail
ListNode curr = head;
if (index + 1 < size - index)
for(int i = 0; i < index + 1; ++i) curr = curr.next;
else {
curr = tail;
for(int i = 0; i < size - index; ++i) curr = curr.prev;
}
return curr.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) {
ListNode pred = head, succ = head.next;
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
ListNode succ = tail, pred = tail.prev;
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
/** 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 is greater than the length,
// the node will not be inserted.
if (index > size) return;
// [so weird] If index is negative,
// the node will be inserted at the head of the list.
if (index < 0) index = 0;
// find predecessor and successor of the node to be added
ListNode pred, succ;
if (index < size - index) {
pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
succ = pred.next;
}
else {
succ = tail;
for (int i = 0; i < size - index; ++i) succ = succ.prev;
pred = succ.prev;
}
// insertion itself
++size;
ListNode toAdd = new ListNode(val);
toAdd.prev = pred;
toAdd.next = succ;
pred.next = toAdd;
succ.prev = toAdd;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
// if the index is invalid, do nothing
if (index < 0 || index >= size) return;
// find predecessor and successor of the node to be deleted
ListNode pred, succ;
if (index < size - index) {
pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
succ = pred.next.next;
}
else {
succ = tail;
for (int i = 0; i < size - index - 1; ++i) succ = succ.prev;
pred = succ.prev.prev;
}
// delete pred.next
--size;
pred.next = succ;
succ.prev = pred;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
- addAtHead，addAtTail： \mathcal{O}(1)O(1)
- get哆窿，addAtIndex链烈，delete：\mathcal{O}(\min(k, N - k))O(min(k,N?k))，其中 kk 指的是元素的索引挚躯。
