本文是力扣 每日一練：LeeCode-707. 設計鏈表 【鏈表+虛擬頭結點+設計】 學習與理解過程，本文僅做學習之用，對本題感興趣的小伙伴可以出門左拐LeeCode-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 。

思路

設置虛擬頭節點

class MyLinkedList {//一句話，一定要保證刪除cur.next,cur為待操作節點的前一個節點//size存儲鏈表元素的個數int size;//虛擬頭結點ListNode dummyHead;public MyLinkedList() {size = 0;dummyHead = new ListNode(0);}public int get(int index) {if(index<0 || index>size-1)return -1;ListNode cur = dummyHead;int i=0;while(i++<=index){cur = cur.next;}return cur.val;    }public void addAtHead(int val) {addAtIndex(0,val);}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;size++; //添加一個元素ListNode cur = dummyHead;for(int i=0;i<index;i++){cur = cur.next;}ListNode add = new ListNode(val);add.next = cur.next;cur.next = add;}public void deleteAtIndex(int index) {if(index<0 || index>=size)return;size--; //減少一個元素if(index==0){dummyHead = dummyHead.next;return;}ListNode cur = dummyHead;for(int i=0;i<index;i++){cur = cur.next;}//當遍歷到index-1的節點（尾節點）cur.next時，還有cur.next.nextcur.next = cur.next.next; //需要考慮邊界尾節點，index>=size}
}/*** 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);*/

時間復雜度: 涉及 index 的相關操作為 O(index), 其余為 O(1)

空間復雜度: O(n)