leetcode設計鏈表,非常工整的實作你值得擁有

設計鏈表的實作，您可以選擇使用單鏈表或雙鏈表，單鏈表中的節點應該具有兩個屬性：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 個節點，

示例：

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 庫，

鏈表:一個包含零個或多個元素的資料結構，每個元素都包含一個值和到另一個元素的鏈接，根據鏈接數的不同，可以分為單鏈表，雙鏈表和多重鏈表，

單鏈表是最簡單的一種，它提供了在常數時間內的 addAtHead 操作和在線性時間內的 addAtTail 的操作，雙鏈表是最常用的一種，因為它提供了在常數時間內的 addAtHead 和 addAtTail 操作，并且優化的插入和洗掉，

雙鏈表在 Java 中的實作為 LinkedList，在 Python 中為 list，這些結構都比較常用，有兩個要點：

哨兵節點：
哨兵節點在樹和鏈表中被廣泛用作偽頭、偽尾等，通常不保存任何資料，

我們將使用偽頭來簡化我們簡化插入和洗掉，在接下來的兩種方法中應用此方法，

雙鏈表的雙向搜索：我們可以從頭部或尾部進行搜索，
單鏈表
讓我們從最簡單的鏈表開始，

class MyLinkedList {
  int size;
  ListNode head;  // sentinel node as pseudo-head
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
  }
}

哨兵節點被用作偽頭始終存在，這樣結構中永遠不為空，它將至少包含一個偽頭，MyLinkedList 中所有節點均包含：值 + 鏈接到下一個元素的指標，

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

addAtIndex，addAtHead 和 addAtTail：
我們首先討論 addAtIndex，因為偽頭的關系 addAtHead 和 addAtTail 可以使用 addAtIndex 來完成，

這個想法很簡單：

找到要插入位置節點的前驅節點，如果要在頭部插入，則它的前驅節點就是偽頭，如果要在尾部插入節點，則前驅節點就是尾節點，
通過改變 next 來插入節點，

toAdd.next = pred.next;
pred.next = toAdd;

deleteAtIndex：
和插入同樣的道理，

找到要洗掉節點的前驅節點，
通過改變 next 來洗掉節點，

// delete pred.next
pred.next = pred.next.next;

get：
從偽頭節點開始，向前走 index+1 步，

// index steps needed 
// to move from sentinel node to wanted index
for(int i = 0; i < index + 1; ++i) curr = curr.next;
return curr.val;

全部代碼：

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class MyLinkedList {
  int size;
  ListNode head;  // sentinel node as pseudo-head
  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 is invalid
    if (index < 0 || index >= size) return -1;

    ListNode curr = head;
    // index steps needed 
    // to move from sentinel node to wanted index
    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 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;

    ++size;
    // find predecessor of the node to be added
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // node to be added
    ListNode toAdd = new ListNode(val);
    // insertion itself
    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 the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    size--;
    // find predecessor of the node to be deleted
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // delete pred.next 
    pred.next = pred.next.next;
  }
}

復雜度分析

時間復雜度：
addAtHead：O(1)
addAtInder，get，deleteAtIndex: O(k)，其中 k指的是元素的索引，
addAtTail：O(N)，其中 N 指的是鏈表的元素個數，
空間復雜度：所有的操作都是 O(1)，