重拾C++之菜鸟刷算法第2篇---链表（上）

链表

��表对于我这个小趴菜来说，真的是从0开始了呀！

一、 理论基础

常见类型 有3种，单链表，双链表，循环链表。

单链表只能指向下一个节点；

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

循环链表，一个指针域，但是链表首尾相连。

面试重要的点：链表的定义

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

ListNode (int x) : val(x), next(NULL){} 这个的写法是显示调用成员变量的构造函数。

也可以写成 ListNode (int x) { val = x; next = NULL; }

// 初始化节点ListNode* head = new ListNode(5);/* 如果没有这一行 ListNode (int x) : val(x), next(NULL){} */ListNode* head = new ListNode();head->val = 5;

二、 移除链表元素

知识点

• 虚拟头节点

  首先创建一个链表，每个节点代表一个小球，节点里有两个部分，一个是小球上的数字（叫做 "值"），另一个是指向下一个节点的箭头。但是，有时候可能会碰到一个问题：第一个小球的位置可能会变化，这会让整个链表的操作变得有点麻烦。虚拟头节点就像是在课桌上放了一个额外的小球，它不代表实际的数据，只是帮忙管理整个链表。这个虚拟头节点始终在链表的最前面，不会变化。这样，无论第一个小球在哪里，链表都有一个始终不变的起点，更方便进行各种操作。

  题目

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

  203. 移除链表元素 - 力扣（LeetCode）

  题解

  /** * 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 *dummyNode = new ListNode(0);       dummyNode->next = head;​       ListNode *cur = dummyNode;       while(cur->next != nullptr){           if(cur->next->val == val){               ListNode *temp = cur->next;               cur->next = cur->next->next;               delete temp;           }           else{               cur = cur->next;           }       }       head = dummyNode->next;       return head;    }};

  三、 设计链表

  知识点

  这个题目涉及到链表的基本操作，包括获取节点值、在头部、尾部和指定位置插入节点，以及删除指定位置的节点。这是编写和理解链表操作的好练习。这道题值得多练习几遍。

  • 链表节点的结构 LinkedNode，以及链表类 MyLinkedList 的构造函数值得学习，可以减少很多不必要的操作。

    节点定义： LinkedNode 的定义提供了一个结构化的方式来表示链表中的每个元素。

    虚拟头节点： 虚拟头节点是一个常见的链表技巧，它在处理链表时可以减少特殊情况的判断，使得代码更加简洁和一致。

    链表初始化： 在构造函数中，链表对象的初始化工作被完成，确保了链表在创建时处于一个良好的初始状态。

    • 关于删除指针的一个小细节

      LinkedNode*tmp = cur->next;cur->next = cur->next->next;delete(tmp);tmp = nullptr;

      在这段代码中，tmp = nullptr; 的操作是为了确保删除节点后，不再持有被删除节点的地址。这是一种良好的编程习惯，尤其是在 C++ 中，避免悬挂指针（dangling pointers）的问题。

      考虑以下情况：

      1. 在 delete(tmp); 之后，tmp 指向的内存已经被释放。

      2. 如果后续的代码中不小心使用了 tmp，那么就会导致悬挂指针问题，可能会访问已释放的内存，引发不可预测的错误。

      通过将 tmp 设置为 nullptr，如果在后续的代码中尝试使用 tmp，会导致空指针访问，从而更容易发现和调试潜在的问题。所以将已删除的指针设置为 nullptr 是一种预防措施，有助于提高代码的健壮性和可维护性。

      题目

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

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

        707. 设计链表 - 力扣（LeetCode）

        题解

        class MyLinkedList {public:    struct LinkedNode {        int val;        LinkedNode* next;        LinkedNode(int x) :val(x), next(nullptr) {}    };​    MyLinkedList() {        m_dummyNode = new LinkedNode(0);        m_size = 0;    }​    int get(int index) {        LinkedNode* cur = m_dummyNode->next;        if (index > m_size - 1 || index next;        }        return cur->val;    }​    void addAtHead(int val) {        LinkedNode* newPoint = new LinkedNode(val);        newPoint->next = m_dummyNode->next;        m_dummyNode->next = newPoint;        m_size++;    }​    void addAtTail(int val) {        LinkedNode* tmp = new LinkedNode(val);        LinkedNode* cur = m_dummyNode;        while (cur->next) {            cur = cur->next;        }        cur->next = tmp;        m_size++;    }​    void addAtIndex(int index, int val) {        if(index > m_size) return;        if(index next;        }        newNode->next = cur->next;        cur->next = newNode;        m_size++;    }​    void deleteAtIndex(int index) {        if (index > m_size - 1 || index next;        }        LinkedNode*tmp = cur->next;        cur->next = cur->next->next;        delete(tmp);        tmp = nullptr;        m_size--;    }private:    int m_size; // 记录链表长度    LinkedNode* m_dummyNode; // 虚拟头节点};​/** * Your MyLinkedList object will be instantiated and called as such: * MyLinkedList* obj = new MyLinkedList(); * int param_1 = obj->get(index); * obj->addAtHead(val); * obj->addAtTail(val); * obj->addAtIndex(index,val); * obj->deleteAtIndex(index); */

        四、 翻转链表

        题外话：我的第一个解法是新建一个列表和一个头节点，然后每遍历一个节点就从前插入。笨鸟先飞，多练练，脑子应该就能想到用双指针了叭~

        知识点

        • 双指针反转问题

          假设链表就是一列玩具火车，任务就是将火车反方向行驶，但是不能改变空间位置，第一个人叫 "prev"（上一个），站在车头前面，开始的时候什么都没有。第二个人叫 "curr"（当前），站在车头上，一开始站在第一个车厢上。还有一个人叫 "nextTemp"（下一个临时），他站在 "curr" 后面，负责看着下一个车厢。要做的事情就是，让 "curr" 不断地从车头跳到车尾。然后nextTemp又及时的将curr拉回到新的车头。

          题目

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

          206. 反转链表 - 力扣（LeetCode）

          题解

          class Solution {public:    ListNode* reverseList(ListNode* head) {        ListNode *cur = head;        ListNode *pre = nullptr;        while(cur){            ListNode *nextTemp = cur->next; // 记住下一节指向            cur->next = pre;            pre = cur;            cur = nextTemp;        }        return pre;    }};

          这一次还记录了题目链接，方便二刷哈哈哈。昨天停了一天，办护照和港澳通行证花了我整整一下午欸，人太多啦~