1.問題描述

你可以選擇使用單鏈表或者雙鏈表，設(shè)計并實現(xiàn)自己的鏈表。

單鏈表中的節(jié)點應(yīng)該具備兩個屬性：val 和 next 。val 是當(dāng)前節(jié)點的值，next 是指向下一個節(jié)點的指針/引用。

如果是雙向鏈表，則還需要屬性 prev 以指示鏈表中的上一個節(jié)點。假設(shè)鏈表中的所有節(jié)點下標(biāo)從 0 開始。

實現(xiàn) MyLinkedList 類：

• MyLinkedList() 初始化 MyLinkedList 對象。
• int get(int index) 獲取鏈表中下標(biāo)為 index 的節(jié)點的值。如果下標(biāo)無效，則返回 -1 。
• void addAtHead(int val) 將一個值為 val 的節(jié)點插入到鏈表中第一個元素之前。在插入完成后，新節(jié)點會成為鏈表的第一個節(jié)點。
• void addAtTail(int val) 將一個值為 val 的節(jié)點追加到鏈表中作為鏈表的最后一個元素。
• void addAtIndex(int index, int val) 將一個值為 val 的節(jié)點插入到鏈表中下標(biāo)為 index 的節(jié)點之前。如果 index 等于鏈表的長度，那么該節(jié)點會被追加到鏈表的末尾。如果 index 比長度更大，該節(jié)點將 不會插入 到鏈表中。
• void deleteAtIndex(int index) 如果下標(biāo)有效，則刪除鏈表中下標(biāo)為 index 的節(jié)點。

示例：

輸入
["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);    // 鏈表變?yōu)?1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 現(xiàn)在，鏈表變?yōu)?1->3
myLinkedList.get(1);              // 返回 3

提示：

• 0 <= index, val <= 1000
• 請不要使用內(nèi)置的 LinkedList 庫。
• 調(diào)用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次數(shù)不超過 2000 。

2.解題思路

使用虛擬頭結(jié)點，這道題目設(shè)計鏈表的五個接口：

• 獲取鏈表第index個節(jié)點的數(shù)值：先判斷index是否合法，index < 0 || index > (size - 1)便不合法。定義一個指針，遍歷：如果直接操作頭結(jié)點，頭結(jié)點值被改了，無法返回頭結(jié)點。

  ListNode* cur = dummyHead->next; 
  while(index) {cur = cur->next;index--;
  }
  return cur->val;
  

  為何臨時指針指針指向dummyHead->next以及循環(huán)如何寫，可帶入一個節(jié)點進(jìn)行驗證。如果index=0，那么相當(dāng)于獲得原始頭結(jié)點的值，while循環(huán)直接跳過之后，return確實合理，那么while循環(huán)以及臨時指針的指向便沒問題。

• 在鏈表的最前面插入一個節(jié)點：在虛擬頭結(jié)點和頭結(jié)點之間插入新節(jié)點就好了

  newNode->next = dummyHead->next;
  dummyHead->next = newNode;
  

  注意以上順序不可變

• 在鏈表的最后面插入一個節(jié)點：cur節(jié)點必須指向最后一個節(jié)點。怎么找尾結(jié)點？

  while(cur->next != nullptr) {cur = cur->next;  //只要不為空，就一直執(zhí)行這句話
  }
  

• 在鏈表第index個節(jié)點前面插入一個節(jié)點

  如果要在第index個節(jié)點錢插入，必須保證第index個節(jié)點為cur->next,也就是cur指向第index個節(jié)點的前一位。只有知道操作節(jié)點的前一個節(jié)點，才能進(jìn)行后續(xù)操作。

  ListNode* cur = dummyHead;
  while(index) {cur = cur->next;index--;
  }
  newNode->next = cur->next;
  cur->next = newNode;
  size++;
  

  檢驗對否，可隨便代入一個節(jié)點便知道。如果index=0，那么while循環(huán)不操作等等進(jìn)行分析。

• 刪除鏈表的第index個節(jié)點

  同理，刪除第index個節(jié)點，必須知道前一個節(jié)點的指針。必須保證第index個節(jié)點為cur->next

  ListNode* cur = dummyHead;
  while(index) {cur = cur->next;index--;
  }
  ListNode* tmp = cur->next; 
  cur->next = cur->next->next;
  delete tmp;
  tmp = nullptr;
  size--;
  

  delete命令指示釋放了tmp指針原本所指的那部分內(nèi)存，被delete后的指針tmp的值（地址）并非就是NULL，而是隨機(jī)值。也就是被delete后，如果不再加上一句tmp=nullptr,tmp會成為亂指的野指針,如果之后的程序不小心使用了tmp，會指向難以預(yù)想的內(nèi)存空間。

3.代碼

C++：

class MyLinkedList {public:struct ListNode {int val;ListNode* next;ListNode(int x): val(x), next(NULL) {}//構(gòu)造函數(shù)};MyLinkedList() {dummyHead = new ListNode(0); // 虛擬頭節(jié)點size = 0;// 初始化單鏈表長度}// 獲取鏈表中第 index個節(jié)點的值:// 獲取到第index個節(jié)點數(shù)值，如果index是非法數(shù)值直接返回-1，// 注意index是從0開始的，第0個節(jié)點就是頭結(jié)點int get(int index) {if(index < 0 || index > (size - 1)) { // 如果 index 不合理，返回 -1return -1;}ListNode* cur = dummyHead->next; //創(chuàng)建一個指針 cur，指向虛擬頭結(jié)點的下一個節(jié)點。//循環(huán)遍歷鏈表，移動 cur 指針到第 index 個節(jié)點處。while(index) {cur = cur->next;index--;}return cur->val;}//在鏈表頭部插入新節(jié)點void addAtHead(int val) {//創(chuàng)建一個新節(jié)點ListNode* newNode = new ListNode(val);//注意以下兩句話的順序newNode->next = dummyHead->next;dummyHead->next = newNode;// 鏈表大小加1。size++;}//在鏈表尾部添加新節(jié)點void addAtTail(int val) {//創(chuàng)建一個新節(jié)點ListNode* newNode = new ListNode(val);//創(chuàng)建一個指針 cur，指向虛擬頭結(jié)點ListNode* cur = dummyHead;//循環(huán)遍歷鏈表，移動 cur 指針到最后一個節(jié)點處while(cur->next != nullptr) {cur = cur->next;}//將最后一個節(jié)點的下一個節(jié)點指向新節(jié)點。cur->next = newNode;size++;}//在指定位置插入新節(jié)點// 在第index個節(jié)點之前插入一個新節(jié)點，例如index為0，那么新插入的節(jié)點為鏈表的新頭節(jié)點。// 如果index 等于鏈表的長度，則說明是新插入的節(jié)點為鏈表的尾結(jié)點// 如果index大于鏈表的長度，則返回空// 如果index小于0，則在頭部插入節(jié)點void addAtIndex(int index, int val) {if(index > size) return;//如果 index 大于鏈表的大小，則直接返回。if(index < 0) index = 0;//如果 index 小于0，則將其設(shè)置為0。ListNode* newNode = new ListNode(val);//創(chuàng)建一個新節(jié)點，并將其值設(shè)置為 val。ListNode* cur = dummyHead;while(index) {cur = cur->next;index--;}newNode->next = cur->next;cur->next = newNode;size++;}// 刪除第index個節(jié)點，如果index 大于等于鏈表的長度，直接return，注意index是從0開始的void deleteAtIndex(int index) {//判斷 index 是否合法，如果不合法，直接返回。if(index >= size ||index < 0) {return;}//創(chuàng)建一個指針 cur，指向虛擬頭結(jié)點。ListNode* cur = dummyHead;while(index) {cur = cur->next;index--;}ListNode* tmp = cur->next; // 創(chuàng)建一個臨時節(jié)點指向即將刪除的節(jié)點cur->next = cur->next->next;// 當(dāng)前節(jié)點指針指向待刪除節(jié)點的下一個節(jié)點delete tmp;// 釋放內(nèi)存//delete命令指示釋放了tmp指針原本所指的那部分內(nèi)存，//被delete后的指針tmp的值（地址）并非就是NULL，而是隨機(jī)值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp會成為亂指的野指針//如果之后的程序不小心使用了tmp，會指向難以預(yù)想的內(nèi)存空間tmp = nullptr;size--;}void printLinkedList() {ListNode* cur = dummyHead;while (cur->next != nullptr) {cout << cur->next->val << " ";cur = cur->next;}cout << endl;}private:int size;ListNode* dummyHead;
};

python：單鏈表

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):self.dummy_head = ListNode()self.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1current = self.dummy_head.nextfor i in range(index):current = current.nextreturn current.valdef addAtHead(self, val: int) -> None:self.dummy_head.next = ListNode(val, self.dummy_head.next)self.size += 1def addAtTail(self, val: int) -> None:current = self.dummy_headwhile current.next:current = current.nextcurrent.next = ListNode(val)self.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = ListNode(val, current.next)self.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = current.next.nextself.size -= 1

python：雙鏈表

class ListNode:def __init__(self, val=0, prev=None, next=None):self.val = valself.prev = prevself.next = nextclass MyLinkedList:def __init__(self):self.head = Noneself.tail = Noneself.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1if index < self.size // 2:current = self.headfor i in range(index):current = current.nextelse:current = self.tailfor i in range(self.size - index - 1):current = current.prevreturn current.valdef addAtHead(self, val: int) -> None:new_node = ListNode(val, None, self.head)if self.head:self.head.prev = new_nodeelse:self.tail = new_nodeself.head = new_nodeself.size += 1def addAtTail(self, val: int) -> None:new_node = ListNode(val, self.tail, None)if self.tail:self.tail.next = new_nodeelse:self.head = new_nodeself.tail = new_nodeself.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returnif index == 0:self.addAtHead(val)elif index == self.size:self.addAtTail(val)else:if index < self.size // 2:current = self.headfor i in range(index - 1):current = current.nextelse:current = self.tailfor i in range(self.size - index):current = current.prevnew_node = ListNode(val, current, current.next)current.next.prev = new_nodecurrent.next = new_nodeself.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returnif index == 0:self.head = self.head.nextif self.head:self.head.prev = Noneelse:self.tail = Noneelif index == self.size - 1:self.tail = self.tail.previf self.tail:self.tail.next = Noneelse:self.head = Noneelse:if index < self.size // 2:current = self.headfor i in range(index):current = current.nextelse:current = self.tailfor i in range(self.size - index - 1):current = current.prevcurrent.prev.next = current.nextcurrent.next.prev = current.prevself.size -= 1