[数据结构与算法]代码随想录算法训练营第三天 | 链表理论基础、203.移除链表元素、707.设计链表、206.反转链表

链表理论基础

什么是链表

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

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

链表的类型

单链表

上述就是单链表

双链表

单链表中的指针域只能指向节点的下一个节点

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点

双链表既可以向前查询，也可以向后查询

循环链表

即链表首尾相连

循环链表可以用来解决约瑟夫环问题

链表在内存中的存储方式

不同于数组，链表在内存中不是连续分布的

链表是通过指针域的指针链接在内存中各个节点

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理

如图链表起始节点是 2，终止节点是 7，各个节点分布在内存的不同地址空间上，通过指针串联一起

链表的定义

卡哥给出的 C++ 定义链表节点方式如下

注意：使用默认构造函数的话，在初始化的时候就不能直接给变量赋值
// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

链表的操作

删除节点

删除 D 节点，如图

只要讲 C 节点的 next 指针指向 E 节点就好

但 D 依然留存在内存中，C++ 中最好是再手动释放掉

添加节点

如图

可以看出链表的添加和删除都是 O(1) 操作，不会影响到其他节点

注意：如果要删除如图第五个节点，需要从头节点查找到第四个节点通过 next 指针进行删除操作，查找的时间复杂度是 O(n)

性能分析

链表特性与数组特性对比如图

• 数组定义时，长度就是固定的，如果需要改动数组长度，需要重新定义一个新的数组

• 链表的长度可以不固定，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景

203.移除链表元素

题目

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

示例：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

补充

删除头节点和非头节点的方式是不一样的

删除头节点：

head = head -> next;

解法

原链表删除元素

1. while 判断头节点不为空 && 同时头节点指向的数值等于要删的值 target

   1. 如果是，就让头节点指向头节点下一个节点，把头节点移除

2. 删除非头节点的元素

   1. 定义指针 cur 指向 head 为了记录 head
   2. cur 与 cur->next 都不能为空
   3. 如果 cur->next 等于 target,就要删掉 cur->next = cur->next->next
   4. 如果不等于，继续遍历

3. 返回 head

class Solution{
public:
    ListNode* removeElements(ListNode* head, int val){
        while (head != NULL && head->val == val){
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }
        
    ListNode* cur = head;
    while(cur != NULL && cur->next != NULL){
        if(cur->next->val == val){
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp
        }else{
            cur = cur->next;
        }
    }
    return head;
}

使用虚拟头节点

1. dummyhead 实例化 dummyhead = new ListNode(0);

2. dummyhead->next 指向 head 头节点的指针是不能改的，不然头节点的值不断改变，最后不能返回

3. 定义指针 cur 指向 dummyhead

4. 后面与上一种方法一样

5. 返回虚拟头节点的下一个节点 dummyhead->next

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = 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;
        delete dummyHead;
        return head;
    }
};

707.设计链表

题目

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

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

提示：

• 所有val值都在 [1, 1000] 之内。

• 操作次数将在 [1, 1000] 之内。

• 请不要使用内置的 LinkedList 库。

解法

注：

• 统一使用虚拟头节点的方式，方便对链表进行增删改操作

• 链表从 0 开始，所以 n <0 和 n>size-1 都不合法

获取第 n 个节点的值

1. 定义一个指针 cur，指向 dummyhead->next

2. while 遍历

3. return cur->next

头部插入节点

重点在于顺序 ，顺序不对的话，会出现 newnode 不能指向头节点的情况

1. newnode = new node()

2. 先让 newnode->next 指向 dummyhead->next

3. 再让 dummyhead->next 指向 newnode

4. size++

尾部插入节点

遍历节点一定要指向尾部节点，这样尾部才能指向 newnode

1. cur = dummyhead

2. 找尾部：遍历到 cur->next 为空，cur 就是尾部节点

3. cur->next = newnode

第 n 个节点前插入节点

一定要知道操作节点的前一个节点的指针，才能进行一个插入节点的操作

1. cur = dummyhead

2. while 遍历找到第 n 个节点

3. 先更新如图 F->D，再更新 C->F

4. size++

删除第 n 个节点

第 n 个节点一定是 cur->next，操作 cur 来删掉第 n 个节点

1. cur = dummyhead

2. 遍历 current->next 找第 n 个节点

3. 删除操作 cur->next = cur->next->next

4. size–

class MyLinkedList {
public:
    struct LinkedNode{
        int val;
        LinkedNode* next;
        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* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size || index < 0){
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= _size||index < 0){
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }

    void printLinkedList(){
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cout << cur->next->val<< " ";
            cur = cur->next;
        }
        cout << endl;
    }
    private:
        int _size;
        LinkedNode* _dummyHead;
};

206.反转链表

题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

提示：

• 链表中节点的数目范围是 [0, 5000]

• -5000 <= Node.val <= 5000

解法

双指针写法

1. 定义指针 cur 指向头节点

2. 再定义指针 pre，在 cur 的前面，pre = NULL

3. while 遍历，当 cur 指向空指针的时候，遍历结束

   1. 需要临时指针 tmp，趁 cur 和下一个节点还连接时，把下一个节点保存
   2. cur->next = pre
   3. pre = cur
   4. cur = tmp

4. return pre 返回新链表的头节点

让 cur 不断指向 pre,并从头遍历过去

纠正：动画应该是先移动 pre,再移动 cur

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; 
        ListNode* cur = head;
        ListNode* pre = NULL;while(cur) {
            temp = cur->next;  
            cur->next = pre; 
            pre = cur;
            cur = temp;}
        return pre;}
};

递归写法

递归的实现逻辑和双指针实现是一一对应的

• 单独写一个函数专门反转链表reverse(cur, pre)是为了实现反转

• 递归遍历过程中 if(cur == NULL)循环终止，终止后头节点是 pre，所以 return pre

  • 同理要保存指向的下一个指针 temp = cur->next
  • cur->next = pre

• 最后 return reverse(temp, cur)是整体向后移一位的递归写法

  • 因为 temp 赋给 cur
  • cur 赋给 pre

力扣上给的输入方式是 reverse list函数，主函数传入一个 head 的头节点

主函数中调用 reverse，来反转列表：

双指针写法的初始化，head 赋给 cur，pre 赋值 NULL

return reverse(head, NULL)
class Solution {
public:
    ListNode* reverse(ListNode* pre, ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(cur, temp);
    }

    ListNode* reverseList(ListNode* head) {
        return reverse(NULL, head);
    }
};