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

链表理论基础

链表的节点由两部分构成，数据域和指针域，数据域存储数据，指针域存储下一个节点的地址。

链表的类型

类型有单链表、双链表，循环链表。

单链表：节点是一个数据域，一个指针域。单向
双链表：节点是一个数据域，两个指针域。双向。一个指针域指向下一节点的地址，一个指针域指向上一个节点的地址。头节点的一个指针域指向空。
循环链表：节点是一个数据域，两个指针域。首尾相连。头节点的一个指针域指向下一个节点的地址，一个指针域指向最后一个节点的地址。

链表的定义

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

// 双向链表节点定义
struct DListNode {
    int val;              // 节点值
    DListNode *prev;      // 指向前驱节点
    DListNode *next;      // 指向后继节点
    DListNode(int x) : val(x), prev(NULL), next(NULL) {}   // 构造函数
};

// 循环单链表节点定义
// 关键区别在于构建时 形成循环
struct CListNode {
    int val;
    CListNode *next;
    CListNode(int x) : val(x), next(NULL) {}
};

// 循环双向链表节点定义   在构建时，令头尾相连
struct CDListNode {
    int val;
    CDListNode *prev;
    CDListNode *next;
    CDListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

不同类型的链表之间的区别

链表的操作

删除节点：当前节点的前一节点的指针指向后一节点的地址，然后释放当前节点内存。
添加节点：先定义新节点，让前一个节点的指针指向新节点，让新节点的指针指向后一个节点的地址，即可完成新节点的添加

图示详解参见：代码随想录-链表理论基础

203.移除链表元素

题目链接：203.移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr) return head;
        ListNode* dummy = new ListNode();   // 定义虚拟节点
        dummy->next = head;  // 虚拟节点指向头节点
        ListNode* cur = head;
        ListNode* pre = dummy;
        while (cur) {
            if(cur->val == val) {     // 找到val
                pre->next = cur->next;   // 删除节点
                delete cur;
                cur = pre->next;  // 下一轮要判断的节点
            }
            else {            // 未找到val, pre和cur都向前移动一步
                pre = cur;   
                cur = cur->next;
            }
            
        } 
        return dummy->next;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)
注意节点的定义和声明写法。

707.设计链表

题目链接：707.设计链表
是个注意细节的题目。

  1. 设计单向链表
class MyLinkedList {

public:
    struct ListNode{     // 定义链表结构体
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(nullptr) {} 
    };

    MyLinkedList() {    // 构造函数，初始化成员变量
        head = nullptr;
        size = 0;
    }
    
    int get(int index) {
        if (index >= size) return -1;    
        if (head == nullptr) return -1;     // // index = 0, size = 0
        ListNode* cur = head;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode* node = new ListNode(val);
        node->next = head;
        head = node;
        size++;    
    }
    
    void addAtTail(int val) {
        ListNode* node = new ListNode(val);
        if (head == nullptr) {
            head = node;
            size++;
            return;
        }
        ListNode* cur = head;
        while (cur) {
            if (cur->next == nullptr) {
                cur->next = node;
                size++;
                break;
            }
            else {
                cur = cur->next;
            }
        }    
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index == size) {
            addAtTail(val);
            return;
        }
        if (index == 0) {
            addAtHead(val);
            return;
        } 
        ListNode* node = new ListNode(val);
        ListNode* pre = head;
        ListNode* cur = head->next;
        index = index - 1;
        while (index--) {
            pre = cur;
            cur = cur->next;
        }
        pre->next = node;
        node->next = cur;
        size++;    
    }
    
    void deleteAtIndex(int index) {
        if (index >= size) return;
        if (index == 0) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
            size--;
            return;
        }
        ListNode* pre = head;
        ListNode* cur = head->next;
        index = index - 1;
        while (index--) {
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
        delete cur;
        size--;
    }
private:
    ListNode* head;
    int size;
};

注意：按索引插入和删除时，循环的次数。

  1. 设计双向链表
class MyLinkedList {

public:
    struct DListNode{     // 定义链表结构体
        int val;
        DListNode* prev;
        DListNode* next;
        DListNode(int x) : val(x), prev(nullptr), next(nullptr) {} 
    };

    MyLinkedList() {    // 构造函数，初始化成员变量
        head = nullptr;
        size = 0;
    }
    
    int get(int index) {
        if (index >= size) return -1;    
        if (head == nullptr) return -1;     // index = 0, size = 0
        DListNode* cur = head;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        DListNode* node = new DListNode(val);
        node->next = head;
        if (head != nullptr) {     // 插入第一个元素时，head为空，就无法用head->prev
            head->prev = node;    // 双向
        }
        head = node;
        size++;    
    }
    
    void addAtTail(int val) {
        DListNode* node = new DListNode(val);
        if (head == nullptr) {
            head = node;
            size++;
            return;
        }
        DListNode* cur = head;
        while (cur) {
            if (cur->next == nullptr) {
                cur->next = node;
                node->prev = cur;    // 双向
                size++;
                break;
            }
            else {
                cur = cur->next;
            }
        }    
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index == size) {
            addAtTail(val);
            return;
        }
        if (index == 0) {
            addAtHead(val);
            return;
        } 
        DListNode* node = new DListNode(val);
        DListNode* pre = head;
        DListNode* cur = head->next;
        index = index - 1;
        while (index--) {
            pre = cur;
            cur = cur->next;
        }
        pre->next = node;
        node->prev = pre;    // 双向
        
        node->next = cur;
        cur->prev = node;   // 双向
        size++;    
    }
    
    void deleteAtIndex(int index) {
        if (index >= size) return;
        if (index == 0) {
            DListNode* tmp = head;
            head = head->next;     
            // head->prev = nullptr;  // 如果原本只有一个节点，head变成nullptr，这里就出错
            if (head != nullptr) {
                head->prev = nullptr;  // 只有 head 不为空时才设置 prev
            }
            delete tmp;
            size--;
            return;
        }
        DListNode* pre = head;
        DListNode* cur = head->next;
        index = index - 1;
        while (index--) {
            pre = cur;
            cur = cur->next;
        }
        pre->next = cur->next;
        // cur->next->prev = pre;     // 如果 cur 是最后一个节点，cur->next 为 nullptr，访问它就崩溃
        if (cur->next != nullptr) {
            cur->next->prev = pre; 
        }
        delete cur;
        size--;
    }
private:
    DListNode* head;
    int size;
};

需要注意：避免空指针访问的情况。

需要熟悉类的定义，构造函数是初始化成员变量的。

使用一个虚拟头节点写这道题，代码会稍微简洁一些。

206.反转链表

题目链接：206.反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* cur = head;
        ListNode* pre = dummy;
        while (cur) {
            ListNode* temp = cur->next;
            if (cur == head) {
                cur->next = nullptr;
            }
            else {
                cur->next = pre;
            }
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)
这道题竟然一次性通过！
我看题解还有另一种方法：递归法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* res = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;  
        return res;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)
递归法着实难理解。。。。。。
但看了卡哥的视频讲解，好像懂了 " _ "
后续遇到递归还需结合着反复琢磨。

# 链表 # c++
Logo
乐奇 Rokid 开放社区

更多推荐

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精

avatar 乐奇 Rokid 开放社区
cover

AI眼镜里面有晶振吗？智能眼镜的时钟系统

avatar 乐奇 Rokid 开放社区
cover

智能眼镜不再只是拍照工具，它正在学会思考、记忆和行动

avatar 乐奇 Rokid 开放社区