算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

203.移除链表元素

题目链接：力扣

思路：删除链表元素与数组不同之处在于，它需要被删除链表元素的前一个元素和后一个元素的参与，而不需要其他元素的参与。

我们使被删除元素前一个元素的指针指向被删除元素的后一个元素，也就是直接跳过被删除的元素，来实现删除。

同时我们考虑到，因为链表最开头的元素没有前一个元素，所以我们需要分两种情况，即被删除元素是第一个元素，或者被删除元素不是第一个元素。

如果不想分两种情况，那我们就该思考如何做到元素统一，应该想到使最开头的元素也拥有前一个元素，我们可以凭空捏造一个。

以下分别是，分两种情况进行删除，和元素统一删除的两种解决方案。

时间复杂度：o(n)

分两种情况的解决方案：

/**
 * 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) {
       //删除头节点
       //此时我们需要定义一个节点替代被删除的节点，因为我们最后要释放被删除节点的空间
       while(head!=NULL&&head->val==val){
           ListNode* tmp=head;
           head=head->next;
           delete tmp;
       }
       //删除其他节点
       //cur先定义为头节点，从头开始
       //我们将通过访问cur的下一个节点，来判断cur的下一个节点是否要被删除
       //如果下一个节点要被删除，那么cur天然就是被删除节点的前一个元素，我们将cur的指针指向它下下个节点
       //我们也需要定义一个节点替代cur的next，以实现释放被删除节点的空间
       ListNode* cur=head;
       while(cur!=NULL&&cur->next!=NULL){
           if(cur->next->val==val){
               ListNode* tmp=cur->next;
               cur->next=cur->next->next;
               delete tmp;
           }
           else{
               //如果cur的下一个节点不用被删除，那么cur往后移动
               cur=cur->next;
           }
       }
       return head;
        
    }
};

将所有节点统一的解决方案：

/**
 * 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;
        dummyhead->next=head;
        //以下代码同
        ListNode* cur=dummyhead;
        while(cur!=nullptr&&cur->next!=nullptr){
            if(cur->next->val==val){
                ListNode* tmp=cur->next;
                cur->next=cur->next->next;
                delete tmp;
            }
            else cur=cur->next;
        }
        //最后记得返回dummyhead->next才是真正的头节点，而不要用head，因为head可能已经被删除
        return dummyhead->next;
    }
};

本题难点在于，我们的是通过当前元素的指针指向下一个元素，来判断下一个元素是否需要被删除，因此遍历整条链表的实际上是前一个元素。最后因为我们要释放被删除的元素，所以创建了一个变量代替它。

707.设计链表

题目：力扣

思路：因为题目中给出了类似于数组的坐标，但实际我们知道链表是没有坐标的，因此我们为链表设计了一个变量长度。

class MyLinkedList {
public:
    //先写一个定义链表节点的结构体
    struct ListNode{
        int val;
        ListNode* next;
        ListNode(int x):val(x),next(nullptr){}
    };
    //MyLinkedList的构造函数，即为成员变量赋值
    MyLinkedList() {
      dummyhead = new ListNode(0);
      //size表示链表的长度
      size = 0;
    }
    //获取位于index坐标处的节点的值
    int get(int index) {
        //考虑坐标不合法的情况
        if(index>(size-1)||index<0) return -1;
        //同样使用目标坐标的前一个节点来访问目标节点
        ListNode* cur=dummyhead;
        while(index!=0){
            cur=cur->next;
            index--;
        }
        return cur->next->val;
    }
    //在链表的头元素之前插入一个元素，即在虚拟头节点和真实头节点中间插入一个元素，不要忘记链表长度加一
    void addAtHead(int val) {
        ListNode* add=new ListNode(val);
        ListNode* tmp=dummyhead->next;
        dummyhead->next=add;
        add->next=tmp;
        size++;
    }
    //在链表的尾部插入一个元素，同样使用一个变量赋值链表长度，来使当前节点移动到尾节点
    void addAtTail(int val) {
        ListNode* add=new ListNode(val);
        int tmp_size=size;
        ListNode* cur=dummyhead;
        while(tmp_size!=0){
            cur=cur->next;
            tmp_size--;
        }
        cur->next=add;
        size++;
    }
    //在指定位置插入节点 首先考虑不合法的坐标
    //然后用一个节点指向cur的下一个节点，因为cur的下一个节点需要更改为新添加的节点add，因此我们无法通过cur->next来访问cur原先的下一个节点
    void addAtIndex(int index, int val) {
        ListNode* add=new ListNode(val);
        if(index>size) return;
        if(index==size) addAtTail(val);
        else{
            ListNode* cur=dummyhead;
            while(index!=0){
                cur=cur->next;
                index--;
            }
            ListNode* tmp=cur->next;
            cur->next=add;
            add->next=tmp;
            size++;
        }
    }
    
    void deleteAtIndex(int index) {
        if(index>size-1) return;
        else{
            ListNode* cur=dummyhead;
            while(index!=0){
                cur=cur->next;
                index--;
            }
            ListNode* tmp=cur->next;
            cur->next=cur->next->next;
            delete tmp;
            size--;
        }
    }
    //MyLinkedList的成员变量，包含一个捏造的虚拟头节点和表示链表长度的size
    private:
    int size;
    ListNode* dummyhead;
};

/**
 * 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);
 */

本题难度我觉得在于链表和类的结合，还有就是把链表当成数组，需要根据索引进行操作。

206.反转链表

题目链接：力扣

思路：因为链表的指针是有指向的，因为我们只要将所有指针的指向反转，那么整个链表也就反转了；

因为一个指针的反转涉及前后两个元素，所以我们采用双指针的方法。

时间复杂度：o(n)

/**
 * 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) {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=NULL){
            ListNode* tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

此题还有递归写法，我对递归不太敏感，对链表也不太熟悉，先留在这，日后再议。文章来源地址https://www.toymoban.com/news/detail-447561.html

到了这里，关于算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！