LeetCode.707设计链表（链表相关操作一篇就够了）

1.问题描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：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 。

2.解题思路

使用虚拟头结点，这道题目设计链表的五个接口：

• 获取链表第index个节点的数值：先判断index是否合法，index < 0 || index > (size - 1)便不合法。定义一个指针，遍历：如果直接操作头结点，头结点值被改了，无法返回头结点。

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

  为何临时指针指针指向dummyHead->next以及循环如何写，可带入一个节点进行验证。如果index=0，那么相当于获得原始头结点的值，while循环直接跳过之后，return确实合理，那么while循环以及临时指针的指向便没问题。

• 在链表的最前面插入一个节点：在虚拟头结点和头结点之间插入新节点就好了

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

  注意以上顺序不可变

• 在链表的最后面插入一个节点：cur节点必须指向最后一个节点。怎么找尾结点？

  while(cur->next != nullptr) {cur = cur->next;  //只要不为空，就一直执行这句话
  }
  

• 在链表第index个节点前面插入一个节点

  如果要在第index个节点钱插入，必须保证第index个节点为cur->next,也就是cur指向第index个节点的前一位。只有知道操作节点的前一个节点，才能进行后续操作。

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

  检验对否，可随便代入一个节点便知道。如果index=0，那么while循环不操作等等进行分析。

• 删除链表的第index个节点

  同理，删除第index个节点，必须知道前一个节点的指针。必须保证第index个节点为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指针原本所指的那部分内存，被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针,如果之后的程序不小心使用了tmp，会指向难以预想的内存空间。

3.代码

C++：

class MyLinkedList {public:struct ListNode {int val;ListNode* next;ListNode(int x): val(x), next(NULL) {}//构造函数};MyLinkedList() {dummyHead = new ListNode(0); // 虚拟头节点size = 0;// 初始化单链表长度}// 获取链表中第 index个节点的值:// 获取到第index个节点数值，如果index是非法数值直接返回-1，// 注意index是从0开始的，第0个节点就是头结点int get(int index) {if(index < 0 || index > (size - 1)) { // 如果 index 不合理，返回 -1return -1;}ListNode* cur = dummyHead->next; //创建一个指针 cur，指向虚拟头结点的下一个节点。//循环遍历链表，移动 cur 指针到第 index 个节点处。while(index) {cur = cur->next;index--;}return cur->val;}//在链表头部插入新节点void addAtHead(int val) {//创建一个新节点ListNode* newNode = new ListNode(val);//注意以下两句话的顺序newNode->next = dummyHead->next;dummyHead->next = newNode;// 链表大小加1。size++;}//在链表尾部添加新节点void addAtTail(int val) {//创建一个新节点ListNode* newNode = new ListNode(val);//创建一个指针 cur，指向虚拟头结点ListNode* cur = dummyHead;//循环遍历链表，移动 cur 指针到最后一个节点处while(cur->next != nullptr) {cur = cur->next;}//将最后一个节点的下一个节点指向新节点。cur->next = newNode;size++;}//在指定位置插入新节点// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度，则返回空// 如果index小于0，则在头部插入节点void addAtIndex(int index, int val) {if(index > size) return;//如果 index 大于链表的大小，则直接返回。if(index < 0) index = 0;//如果 index 小于0，则将其设置为0。ListNode* newNode = new ListNode(val);//创建一个新节点，并将其值设置为 val。ListNode* cur = dummyHead;while(index) {cur = cur->next;index--;}newNode->next = cur->next;cur->next = newNode;size++;}// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的void deleteAtIndex(int index) {//判断 index 是否合法，如果不合法，直接返回。if(index >= size ||index < 0) {return;}//创建一个指针 cur，指向虚拟头结点。ListNode* cur = dummyHead;while(index) {cur = cur->next;index--;}ListNode* tmp = cur->next; // 创建一个临时节点指向即将删除的节点cur->next = cur->next->next;// 当前节点指针指向待删除节点的下一个节点delete tmp;// 释放内存//delete命令指示释放了tmp指针原本所指的那部分内存，//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间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