代码随想录算法训练营第3天 | 链表基础，203.移除链表元素，707.设计链表，206.反转链表

链表理论

链表，顾名思义，是链状的数据的集合。在计算机编程语言当中，链表通常的表现形式为：

单链表，图源自代码随想录

根据不同的节点构成，链表可以被分为：

• 单链表

如上面的图所示，即为单链表，“单”指的是单向，即一个节点除了所存储的数据外，只保留其下一个节点的指针。

• 双链表

在单链表的基础上，在每个节点上增加一个指向上一个节点的指针，将根据这个节点能查询到的节点扩展为前后节点。

双向链表

• 循环链表

在双链表或者单链表的基础上，使链表首尾相连，就形成了一个循环链表。

循环链表

链表的存储方式与数组不同，数组通常是连续存储的，通过索引和数组起始位置即可以\(O(1)\)的时间访问到指定的数据，但链表中的节点不是连续存储的，需要从链首指针开始，依次查询到指定位置才可以，需要花费\(O(n)\)的时间。

链表存储示意图

根据链表的定义，一个常见的单链表的节点可以用C++表示为：

struct Node* {
    int data;   // 该节点所存储的数据
    Node* next; // 指向下一个节点的指针
    Node(int x) : data(x), next(nullptr) {}  // 节点的构造函数，可选
};

一个常见的双链表节点可以用C++表示为：

struct Node* {
    int data;   // 该节点所存储的数据
    Node* prev; // 指向前一个节点的指针
    Node* next; // 指向下一个节点的指针
    Node(int x) : data(x), prev(nullptr), next(nullptr) {}  // 节点的构造函数，可选
};

203.移除链表元素

代码随想录链接

题目

LeetCode-203

删除链表中等于给定值的所有节点。

自己的想法

自己首先想到的还是使用链表原有的头和尾来完成，对头进行单独的判断处理，如果头携带值就等于给定值，则不断地把头设置为下一个节点，当头所携带的值不是给定值之后，再对链表后面进行处理，自己写的版本即为解法一。

解法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* cur = NULL; // 为了保存当前使用的节点而设立的一个指针
        while (head != NULL && head -> val == val) { // 如果头指针指向的节点携带的值等于给定值
            cur = head;  // 保存头结点的地址
            head = head -> next;  // 将头指向下一个节点，使下一个节点成为头结点，这一步之后原来的头结点已经被剥离链表
            delete cur;  // 释放掉原来头结点的空间
        }
        cur = head; // 从头结点开始遍历，此时头结点的值不等于给定值，所以我们下面只需要看cur -> next的值是否等于给定值
        while (cur != NULL) { // 当遍历节点不为空时
            if (cur -> next != NULL && cur -> next -> val == val) { // 如果当前节点存在下一个节点且下一个节点的数据等于给定值
                ListNode* toDel = cur -> next;  // 标记需要被删除的节点
                cur -> next = toDel -> next;    // 更新当前节点的next指针，将其指向被删除节点的下一个节点，此步之后被删除节点已被剥离链表
                delete toDel;                   // 释放被删除节点的空间
            } else {                            // 如果当前节点的下一个节点不存在或者其值不等于给定值
                cur = cur -> next;              // 则移动节点
            }
        }
        return head;                            // 返回链表表首指针
    }
};

由于遍历了整个链表，故时间复杂度为\(O(n)\)，使用了常数个额外变量，空间复杂度为\(O(1)\)。

解法二

下面这种方法的思想和上面是一样的，只不过使用了一个假表首来使得代码实现起来比较简单。之前学过但是自己想的时候就是想不起来这种做法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(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* toDel = cur -> next;
                cur -> next = toDel -> next;
                delete toDel;
            } else {
                cur = cur -> next;
            }
        }
        head = dummyHead -> next;
        delete dummyHead;
        return head;
    }
};

由于遍历了整个链表，故时间复杂度为\(O(n)\)，使用了常数个额外变量，空间复杂度为\(O(1)\)。

707.设计链表

代码随想录链接

题目

Leetcode-707

就是实现链表的增删查功能，改太简单了。上过数据结构的同学应该能非常熟练地完成才对。

自己的思考

尽量地多使用伪表首来实现功能，让代码的逻辑看起来更清晰一些。

解法

class MyLinkedList {
public:
    struct Node {
        int val;
        Node* next;
        Node(int val): val(val), next(nullptr){}
    };

    MyLinkedList() {
        _dummyHead = new Node(0);                       // 内部实现一个假表首
        _size = 0;                                      // 内部的变量，用于存储当前链表的大小
    }
    
    int get(int index) {
        if (index >= _size || index < 0) return -1;     // 在index不正确时，按照题目要求返回-1
        Node* cur = _dummyHead -> next;                 // 声明一个用于遍历链表的节点
        while (index--) cur = cur->next;                // 根据index定位到节点
        return cur -> val;                              // 返回节点值
    }
    
    void addAtHead(int val) {
        Node* toAdd = new Node(val);                    // 实例化一个新的节点来存储值
        toAdd -> next = _dummyHead -> next;             // 将新的节点的next指针指向当前的（真）头指针，让头节点成为其下一个节点
        _dummyHead -> next = toAdd;                     // 将假表首的next指针指向新的节点，代表新节点成为了（真）头指针
        _size++;                                        // 别忘了更新链表的大小
    }
    
    void addAtTail(int val) {
        Node* cur = _dummyHead;                         // 依次遍历到链表的末尾，实例化一个新的节点，并将原末尾节点的next指针指向新的节点
        while (cur -> next != NULL) cur = cur -> next;
        Node* toAdd = new Node(val);
        cur -> next = toAdd;
        _size++;
    }
    
    void addAtIndex(int index, int val) {               // 类似于get函数的做法，先定位到index指向的节点，然后根据题意将节点插入在该节点之前（修改前节点的next指针和新节点的next指针）
        if (index > _size) return;
        if (index < 0) index = 0;
        Node* toAdd = new Node(val);
        Node* cur = _dummyHead;
        while (index--) cur = cur -> next;
        toAdd -> next = cur -> next;
        cur -> next = toAdd;
        _size++;
    }
    
    void deleteAtIndex(int index) {                     // 根据index定位到节点，通过将前一个节点的next指针修改为要删除节点的下一个节点的地址来完成删除
        if (index >= _size || index < 0 ) return;
        Node* cur = _dummyHead;
        while (index--) cur = cur -> next;
        Node* todel = cur -> next;
        cur -> next = todel -> next;
        delete todel;                                   // 释放节点空间
        _size--;
    }

private:
    int _size;
    Node* _dummyHead;
};

206.反转链表

代码随想录链接

题目

LeetCode-206

将一个给定的单链表的节点顺序依次翻转过来。

自己的思考

首先想到的是生成一个新的链表，依次分别将原链表中的数据不断在新链表的头部进行添加。但考虑到这样会造成额外的空间开销，就考虑使用链表的现有节点进行逆转。

解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) return NULL;              // 处理空表的特殊情况
        if (head -> next == NULL) return head;      // 处理只有一个节点的特殊情况
        ListNode* dummyHead = new ListNode(0);      // 使用假表首
        ListNode* cur = head;                       // 使用一个当前节点的指针
        while (cur != NULL) {                       // 循环条件
            ListNode* tmp = cur;                    // 使用一个临时指针来标记当前节点A
            cur = cur -> next;                      // 将当前节点向后移动，标记原链表中A的下一个节点
            tmp -> next = dummyHead -> next;        // 将A的next指针指向假表首的下一个节点
            dummyHead -> next = tmp;                // 使A成为新的表首
        }
        return dummyHead -> next;                   // 真表首是假表首的next指针所指向的节点
    }
};

遍历了链表，时间复杂度为\(O(n)\)；由于没有产生新的链表，空间复杂度为\(O(1)\)。