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

smq77 / 2024-11-05 / 原文

链表基础

链表分为单链表、双链表和循环链表，链表在内存中与数组不同，不是连续存储的。

C++中链表的定义方式如下：

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

这里引用代码随想录卡哥总结的数组和链表的区别：

6-203.移除链表元素

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

示例 1：

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

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 10⁴] 内
1 <= Node.val <= 50
0 <= val <= 50

删除头节点和非头节点的操作是不一样的，这样会导致程序写起来较为复杂，首先给出一个使用不同操作来删除的代码：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head != NULL && head->val == val){//删除头结点
            ListNode* tmp =  head;//这里要临时创建一个tmp以便于后续释放空间
            head = head -> next;
            delete tmp;//释放内存
        }
        
        ListNode* cur = head;
        while(cur != NULL && cur->next!= NULL){//删除非头结点
            if(cur->next->val == val){
                ListNode* tmp = cur->next;//临时创建一个tmp以便于后续释放空间
                cur->next = cur->next->next;
                delete tmp;//释放内存
            }else{
                cur = cur->next;
            }
        }
        return head;
    }
};

删除头节点，首先判断头节点是否为空，如果为空则直接返回，当头节点指向的值为target的时候，我们删除头节点，删除前记得创建一个临时指针便于后续释放空间。

然后就可以定义一个cur来指向目前的头节点，对后续节点进行操作了。

删除后续节点，依旧判断是否为空，为空则返回，不为空且下一节点不为空时，判断指向的值是否为target，是则删除当前节点，释放空间cur向后移动一位，不是则直接向后移动一位。最后返回head即可。

使用虚拟头节点

使用虚拟头节点的好处是，当我们使用后，就可以使用统一的判断逻辑来操作后续所有节点，无需像上述代码一样需要预先判断是否为头节点。使用虚拟头节点的代码如下所示：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyhead= new ListNode(0);
        dummyhead -> next = head;
        ListNode* cur = dummyhead;
        while(cur != NULL && cur->next!= NULL){//删除结点
            if(cur->next->val == val){
                ListNode* tmp = cur->next;//临时创建一个tmp以便于后续释放空间
                cur->next = cur->next->next;
                delete tmp;//释放内存
            }else{
                cur = cur->next;
            }
        }
        head = dummyhead->next;
        delete dummyhead;
        return head;
    }
};

在使用链表时，多画图可以帮助理解为什么有些地方指向next更好，有些地方则是直接指向目标。这里在最后返回时有一个需要注意的点，就是head可能已经被我们删除了，那么此时链表的头其实是dummyhead指向的下一个位置。

7-707.设计链表

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

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

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

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

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

设计链表问题，要求对链表有较好的掌握，第一次看还是有点晕，以前完全没学过链表这个类型，遇到了相当的困难，不过还是跟着视频写下来了。这里就只贴代码了，二刷再复习思路。

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--){ // 如果--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++;
    }
    // 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果index大于链表的长度，则返回空
    // 如果index小于0，则在头部插入节点
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0;
        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;
        tmp = nullptr;
        _size--;
    }
    private:
    int _size;
    LinkedNode* _dummyHead;
};

8-206.反转链表

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

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

双指针法：使用双指针从前向后遍历，使用tmp指针来暂时存储节点地址。代码如下

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* tmp;
        ListNode* pre = NULL;
        while(cur){
            tmp = cur->next;//保存节点
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

递归法：与双指针法其实道理相同，但是代码本体更加简洁。这里第一次接触到递归，我个人感觉其特点是，首先要设置一个跳出循环的判断，类似于while循环，其次在函数中再次引用自己，类似于套娃的结构。

class Solution {
public:

    ListNode* reverse(ListNode* cur,ListNode* pre) {
        if(cur == NULL) return pre;
        ListNode* tmp = cur->next;
        cur->next = pre;
        return reverse(tmp,cur);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(head,NULL);
    }
};