1.問(wèn)題描述

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

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

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

實(shí)現(xiàn) MyLinkedList 類：

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

示例：

輸入
["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
• 請(qǐng)不要使用內(nèi)置的 LinkedList 庫(kù)。
• 調(diào)用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次數(shù)不超過(guò) 2000 。

2.解題思路

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

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

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

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

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

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

  注意以上順序不可變

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

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

• 在鏈表第index個(gè)節(jié)點(diǎn)前面插入一個(gè)節(jié)點(diǎn)

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

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

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

• 刪除鏈表的第index個(gè)節(jié)點(diǎn)

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