代码随想录DAY3 203.移除链表元素、707.设计链表、206.反转链表

链表理论基础

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

1. 链表的定义：

• 一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）

• 链接的入口节点称为链表的头结点也就是head
  

2. 链表的类型

• 单链表：指针域只能指向节点的下一个节点，如上图。

• 双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。既可以向前查询也可以向后查询。
  

• 循环链表：链表首尾相连

3. 链表的存储方式

• 链表是通过指针域的指针链接在内存中各个节点，所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

. 4. 链表的操作

• 删除结点：C++最好手动释放删除结点的内存[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rd20xill-1666958413596)(F:\代码随想录\Day3\删除结点.png)]
• 添加结点：
  

5. 性能分析：

   

203. 移除链表元素

题目链接：https://leetcode.cn/problems/remove-linked-list-elements/

文章讲解：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

视频讲解：https://www.bilibili.com/video/BV18B4y1s7R9

• 题目：

  给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点

  • 可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6y0tdadF-1666958413597)(F:\代码随想录\Day3\移除头节点.png)]

class Solution {
  public:
      ListNode* removeElements(ListNode* head, int val) {
          ListNode* dummyHead = new ListNode(0, head);
          ListNode* cur = dummyHead;
          while (cur->next != NULL) {
              if (cur->next->val == val) {
                  ListNode* tmp = cur->next;
                  cur->next = cur->next->next;
                  delete tmp;
              } else {
                  cur = cur->next;
              }
          }
          head = dummyHead->next;
          return head;
      }
  };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

707、设计链表

题目链接：https://leetcode.cn/problems/design-linked-list/

文章讲解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

视频讲解：https://www.bilibili.com/video/BV1FU4y1X7WD

• 题目：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点

  class MyLinkedList {
  public:
      struct LinkedNode{
          int val;
          LinkedNode* next;
          LinkedNode() : val(0), next(nullptr) {}
          LinkedNode(int val) : val(val), next(nullptr) {}
      };
  
      MyLinkedList() {
          dummyHead = new LinkedNode(0);
          _size = 0;
      }
      
      int get(int index) {
          if (index > (_size - 1) || index < 0) {
              return -1;
          }
          LinkedNode* cur = dummyHead->next;
          while (index--) {
              cur = cur->next;
          }
          return cur->val;
      }
      
      void addAtHead(int val) {
          LinkedNode* head = new LinkedNode(val);
          head->next = dummyHead->next;
          dummyHead->next = head;
          _size++;
      }
      
      void addAtTail(int val) {
          LinkedNode* tmp = new LinkedNode(val);
          LinkedNode* cur = dummyHead;
          while (cur->next != nullptr) {
              cur = cur->next;
          }
          cur->next = tmp;
          _size++;
      }
      
      void addAtIndex(int index, int val) {
          LinkedNode* tmp = new LinkedNode(val);
          if (index > _size) {
              return;
          } else if (index <= 0) {
              tmp->next = dummyHead->next;
              dummyHead->next = tmp;
          } else {
              LinkedNode* cur = dummyHead;
              while (index--) {
                  cur = cur->next;
              }
              tmp->next = cur->next;
              cur->next = tmp;
          }
          _size++;
      }
      
      void deleteAtIndex(int index) {
          LinkedNode* cur = dummyHead;
          if (index < 0 || index >= _size) {
              return;
          }
          while (index--) {
              cur = cur->next;
          }
          LinkedNode* tmp = cur->next;
          cur->next = cur->next->next;
          delete tmp;
          _size--;
      }
  
  private:
      int _size;
      LinkedNode* dummyHead;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78

206、反转链表

题目链接：https://leetcode.cn/problems/reverse-linked-list/

文章讲解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

视频讲解：https://www.bilibili.com/video/BV1nB4y1i7eL

• 题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = NULL;
        ListNode* tmp = NULL;
        while (cur != nullptr) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15