leetcode 203 移除链表元素

àì夳堔傛蜴生んèń 2022-09-08 11:51 173阅读 0赞

## 前言 ##

题目：[203. 移除链表元素][203.]

参考答案：[移除链表元素-力扣官方题解][-]、[移除链表元素-代码随想录][- 1]

本文档详细代码见：[git仓库][git]

--------------------

## 提交代码 ##

我感觉list头节点存储元素并不是一个好的做法。因为，节点的增删都可能导致头结点的修改。对于单链表而言，头结点没有前驱节点，导致头结点需要单独操作。

下面四个代码，可以分为`头结点不存储元素`和`头结点存储元素`两大类。头结点不存储元素，头结点可以放在栈中也可以放在堆中。头结点存储元素，可以直接处理链表，或者添加伪头结点。

### 头结点不存储元素-头结点在栈中 ###

头节点存储在栈中，是无意间这样写出来的，因为太旧没写链表的代码了。如果头结点在栈中，释放节点的时候，不用考虑头节点，它会自动弹栈回收。总的来说，头结点和其他节点一样在堆中，栈中使用一个指针指向头结点，比较好，比较统一。但既然写出头结点在栈中，不妨把代码在下面列出来。

#include <iostream>
    #include <vector>
    #include <list>
    
    using namespace std;
    
    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) {
            // 题目要求的链表，表头包含数据，没关系，传递head->next进来就好
    
            // 寻找第一个非val节点
            while(head!=nullptr && head->val==val){
                ListNode* nextHead = head->next;
                delete head;
                head = nextHead;
            }
    
             // 如果是空链表,直接返回
            if(head == nullptr)
                return head;
            
            // 头节点已经是非val了。删除非头结点的其他val
            ListNode* it=head->next; ListNode* beforeIt=head; ListNode* nextIt;
            while(it!=nullptr){
                nextIt = it->next;
                if(it->val == val){
                    delete it;
                    beforeIt->next = nextIt; // 删除节点会断裂链表，这里给续上;并且beforeIt不需要移动
                    it = nextIt;
                }else{
                    beforeIt = beforeIt->next;
                    it = nextIt;
                }   
            }
            return head;
        }
    };
    
    
    int main(void){
        vector<int> tmpVec = {7,1,7,2,3,5,7,7}; int val = 7;
    
        ListNode head; // 链表头节点，不存储数据
    
        ListNode* it = &head;
    
        // // 初始化一个链表
         最开始敲代码的时候，我是这么写的，但是程序会陷入死循环。我调试的时候，发现it指针不动。
         问题在于，创建node这一局部变量。当再次循环到它时候，使用新的num值，替换原来对象中的值。但仍然是同一个对象，只是里面的值变了而已。这导致next指向了自己。
         根本原因是不是：node在栈中创建之后，循环时变量不会重复分配？？
        // for( auto num : tmpVec){
        //     ListNode node(num);
        //     it->next = &node;
        //     it = it->next;
        // }
    
        // 初始化一个链表
        for( auto num : tmpVec){
            ListNode* node = new ListNode(num); // 在堆中申请空间
            it->next = node;
            it = it->next;
        }
    
        // 测试代码
        Solution s;
        it = s.removeElements(head.next,val);
        head.next = it; // removeElements里面察觉不到外面的head，需要给续上
    
        // 遍历链表
        it = &head;
        for(it; it->next!=nullptr; it=it->next)
            cout<<it->next->val<<" ";
        cout<<endl;
    
        // 释放链表
        it = &head; it = it->next;  ListNode* nextIt;
        for(; it!=nullptr;){
            nextIt = it->next; // 站在下一个位置，等待干完清除工作后回来
            delete it;
            it = nextIt;
        }
    }

### 头结点不存储元素-头结点在堆中 ###

这是比较常规的写法，链表所有节点都在堆中，表头不存储元素。

#include <iostream>
    #include <vector>
    #include <list>
    
    using namespace std;
    
    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) {
            // 题目要求的链表，表头包含数据，没关系，传递head->next进来就好
    
            // 寻找第一个非val节点
            while(head!=nullptr && head->val==val){
                ListNode* nextHead = head->next;
                delete head;
                head = nextHead;
            }
    
             // 如果是空链表,直接返回
            if(head == nullptr)
                return head;
            
            // 头节点已经是非val了。删除非头结点的其他val
            ListNode* it=head->next; ListNode* beforeIt=head; ListNode* nextIt;
            while(it!=nullptr){
                nextIt = it->next;
                if(it->val == val){
                    delete it;
                    beforeIt->next = nextIt; // 删除节点会断裂链表，这里给续上;并且beforeIt不需要移动
                    it = nextIt;
                }else{
                    beforeIt = beforeIt->next;
                    it = nextIt;
                }   
            }
            return head;
        }
    };
    
    
    int main(void){
        vector<int> tmpVec = {7,1,7,2,3,5,7,7}; int val = 7;
    
        ListNode* head = new ListNode(); // 链表头节点，不存储数据
        ListNode* it = head;
    
        // 初始化一个链表
        for( auto num : tmpVec){
            ListNode* node = new ListNode(num); // 在堆中申请空间
            it->next = node;
            it = it->next;
        }
    
        // 测试代码
        Solution s;
        it = s.removeElements(head->next,val);
        head->next = it;
    
        // 遍历链表
        it = head;
        for(it; it->next!=nullptr; it=it->next)
            cout<<it->next->val<<" ";
        cout<<endl;
    
        // 释放链表
        it = head; ListNode* nextIt;
        for(; it!=nullptr;){
            nextIt = it->next; // 站在下一个位置，等待干完清除工作后回来
            delete it;
            it = nextIt;
        }
    }

### 头结点存储元素-直接处理链表 ###

头结点存储元素，头结点需要单独处理，因为元素的增删都可能导致头结点位置的变化。同时，在初始化填充链表的时候，需要单独判断初始化的链表是否为空，为空则可能不需要申请节点。这就略微有点麻烦。

#include <iostream>
    #include <vector>
    #include <list>
    
    using namespace std;
    
    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) {
            // 寻找第一个非val节点
            while(head!=nullptr && head->val==val){
                ListNode* nextHead = head->next;
                delete head;
                head = nextHead;
            }
    
             // 如果是空链表,直接返回
            if(head == nullptr)
                return head;
            
            // 头节点已经是非val了。删除非头结点的其他val
            ListNode* it=head->next; ListNode* beforeIt=head; ListNode* nextIt;
            while(it!=nullptr){
                nextIt = it->next;
                if(it->val == val){
                    delete it;
                    beforeIt->next = nextIt; // 删除节点会断裂链表，这里给续上;并且beforeIt不需要移动
                    it = nextIt;
                }else{
                    beforeIt = beforeIt->next;
                    it = nextIt;
                }   
            }
            return head;
        }
    };
    
    
    int main(void){
        const vector<int> tmpVec = {7,1,7,2,3,5,7,7}; int val = 7;
    
        ListNode* head = nullptr; // 链表头节点,存储数据
        ListNode* it = head;
    
        // 初始化一个链表
        if(tmpVec.empty()){
            goto test;
        }
    
        if(tmpVec.size() >= 1){
            head = new ListNode();
            it = head;
            head->val = tmpVec[0]; // 单独给头结点赋值
            for(int i=1; i<tmpVec.size(); i++){
                ListNode* node = new ListNode(tmpVec[i]); // 在堆中申请空间
                it->next = node;
                it = it->next;
            }
            goto test;
        }
    
    test:
    
        // 测试代码
        Solution s;
        head = s.removeElements(head,val); // 头结点可能被删除了，这里得到头结点指针
    
        // 遍历链表
        it = head;
        for(it; it!=nullptr; it=it->next)
            cout<<it->val<<" ";
        cout<<endl;
    
        // 释放链表
        it = head; ListNode* nextIt;
        for(; it!=nullptr;){
            nextIt = it->next; // 站在下一个位置，等待干完清除工作后回来
            delete it;
            it = nextIt;
        }
    }

### 头结点存储元素-添加伪头结点 ###

这个做法是我没想到的。确实变通。当头结点存储元素操作不方便的时候，我们可以添加一个伪头结点。这个想法挺好。

#include <iostream>
    #include <vector>
    #include <list>
    
    using namespace std;
    
    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,head); // 创建一个伪头结点
            
            ListNode* it = dummyHead->next;
            ListNode* beforeIt = dummyHead;
            ListNode* nextIt = nullptr;
            while(it!=nullptr){
                nextIt = it->next;
                if(it->val == val){
                    delete it;
                    beforeIt->next = nextIt;
                    it = nextIt;
                }else{
                    beforeIt = it;
                    it = nextIt;
                }
            }
    
            ListNode* result = dummyHead->next;
            delete dummyHead;
            return result;
        }
    };
    
    
    int main(void){
        const vector<int> tmpVec = {7,1,7,2,3,5,7,7}; int val = 7;
    
        ListNode* head = nullptr; // 链表头节点,存储数据
        ListNode* it = head;
    
        // 初始化一个链表
        if(tmpVec.empty()){
            goto test;
        }
    
        if(tmpVec.size() >= 1){
            head = new ListNode();
            it = head;
            head->val = tmpVec[0]; // 单独给头结点赋值
            for(int i=1; i<tmpVec.size(); i++){
                ListNode* node = new ListNode(tmpVec[i]); // 在堆中申请空间
                it->next = node;
                it = it->next;
            }
            goto test;
        }
    
    test:
    
        // 测试代码
        Solution s;
        head = s.removeElements(head,val); // 头结点可能被删除了，这里得到头结点指针
    
        // 遍历链表
        it = head;
        for(it; it!=nullptr; it=it->next)
            cout<<it->val<<" ";
        cout<<endl;
    
        // 释放链表
        it = head; ListNode* nextIt;
        for(; it!=nullptr;){
            nextIt = it->next; // 站在下一个位置，等待干完清除工作后回来
            delete it;
            it = nextIt;
        }
    }

[203.]: https://leetcode-cn.com/problems/remove-linked-list-elements/
[-]: https://leetcode-cn.com/problems/remove-linked-list-elements/solution/yi-chu-lian-biao-yuan-su-by-leetcode-sol-654m/
[- 1]: https://leetcode-cn.com/problems/remove-linked-list-elements/solution/203-yi-chu-lian-biao-yuan-su-zhi-jie-sha-6h6v/
[git]: https://github.com/da1234cao/data_structure/tree/master/leetcode