小工具知识网

当前位置: 首页 > 行业知识 > 代码算法训练营day3 | 203移除链表元素、707设计链表、206反转链表

行业知识

代码算法训练营day3 | 203移除链表元素、707设计链表、206反转链表

2026-11-17 23:10:17 来源:互联网转载

day3:

  • 203移除链表元素
  • 707设计链表
  • 206反转��表

    203移除链表元素

    题目链接

    状态:

    文档:programmercarl.com

    思路:

    有两种办法,一种是不用虚拟头节点,要分两种情况讨论。(删除头节点和非头节点)

    一种是用虚拟头节点,不用分情况讨论。

    很显然第二种比较方便,并且虚拟头节点也是经常使用的,所以选择用这种方法。

    虚拟头节点,顾名思义,就是代替了原有的头节点,所以dummyhead -> next = head;

    因为要遍历链表中的每一个元素,来判断是否和要寻找的目标元素的值相等,可以选择一直使用head->next ->value== val;来进行判断,但这样的话head就不能参与判断了,所以又会走入第一种办法的漩涡中。所以这里要添加一个指针cur,指向dummyhead,通过不断的cur->next->value ==val;来进行判断。

    代码:

    /** * 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(0); //创建虚拟节点        dummyhead->next = head; //让虚拟节点变成虚拟头节点        ListNode* cur = dummyhead; //设置一个临时的遍历变量,指向虚拟头节点        //开始遍历        while(cur!=NULL && cur->next!=NULL)        {            //如果匹配成功了            if(cur->next->val == val)            {                ListNode* tmp = cur->next; //保存一下这个节点                //改变目标值前一个值的next的值                cur->next = cur->next->next;                delete tmp; //释放目标值            }            else{                cur = cur->next;            }        }        //全部遍历完,结果处理        head = dummyhead->next;        delete dummyhead;        return head;    }};

    注意: 不要忘记最后删除掉虚拟头节点。


    707设计链表

    题目链接

    状态:

    文档:programmercarl.com

    实现过程中的问题:

    ①在实现//将一个值插入到下标为index的节点之前 void addAtIndex(int index, int val)函数的时候,忘记了分类讨论:如果index大于链表的长度,则返回空。如果index小于0,则在头部插入节点。

    ②在实现//删除链表中下标为index的节点 void deleteAtIndex(int index)函数的时候,忘记将创建出来的临时变量用完后置为空,delete命令指示释放了tmp指针原本所指的那部分内存,被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后,如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针,如果之后的程序不小心使用了tmp,会指向难以预想的内存空间。

    代码:

    class MyLinkedList {public:    // 定义链表结构体    struct LinkedNode {        int val;        LinkedNode* next;        LinkedNode(int val) : val(val), next(nullptr) {}    };    MyLinkedList() {        // 设置一个虚拟头节点        dummy_head = new LinkedNode(0);        size = 0;    }    // 获取下标为index的节点的值,下标无效返回-1    int get(int index) {        if (index  (size - 1))            return -1;        //dummy_head->next = head; //设定虚拟头节点        // 因为要遍历元素,所以设置一个临时变量cur,指向头节点        LinkedNode* cur = dummy_head->next; //cur指向头节点        while (index--) { //index==0 时跳出while循环            cur = cur->next;        }        return cur->val;    }    //将一个值插入到链表中第一个元素之前    void addAtHead(int val) {        //变成头节点        LinkedNode* newNode = new LinkedNode(val);        newNode->next = dummy_head->next;        dummy_head->next = newNode;        size++;    }    //将一个值追加到最后一个元素之后    void addAtTail(int val) {        //变成最后一个节点        LinkedNode* newNode = new LinkedNode(val);        LinkedNode* cur = dummy_head;        while(cur->next!=NULL) //cur的下一个还有数的时候        {            cur = cur->next;        }        //此时cur指向最后一个数        cur->next = newNode;        size++;    }    //将一个值插入到下标为index的节点之前    void addAtIndex(int index, int val) {        //也就是插入到index的位置上        if(index > size) return;        if(index next;        }        newNode->next = cur->next;        cur->next = newNode;        size++;    }    //删除链表中下标为index的节点    void deleteAtIndex(int index) {        if(index >= size || index next指向的节点        while(index--)        {            cur = cur->next;        }        //创建新的节点存放被删除的那个节点        LinkedNode* tmp = cur->next;        cur->next = cur->next->next;        size--;        delete tmp;        //delete命令指示释放了tmp指针原本所指的那部分内存,        //被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后,        //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针        //如果之后的程序不小心使用了tmp,会指向难以预想的内存空间        tmp = NULL;    }private:    int size;               // 链表长度    LinkedNode* dummy_head; // 虚拟头节点};/** * 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反转链表

    题目链接

    状态:

    文档:programmercarl.com

    思路:

    把指针的箭头调个头,就很容易了。代码中实现的是第二行。

    因为反转后,原来的节点就有新的next指向的值了,所以要新建一个节点pre去存放每个节点反转后的新的next。

    又因为原来节点的next指向改变了,所以需要一个临时指针tmp来存放这个节点原来存放的next的节点,不然到后面节点会丢失。

    实现过程中的问题:

    ①在while循环中,

     tmp = cur->next; //存放节点原来的next cur->next = pre; //改变指向//我写把左值和右值写反了,经常会出现这种错误!!!//错误写法:cur->next = tmp;pre = cur->next;

    ②还是在while循环中,

    pre = cur;cur = tmp;//两个赋值顺序写错了,//错误写法:cur = tmp;pre = cur;//很明显就不对,应该在cur被赋值之前就先赋值给pre才行,大意了。

    代码:

    /** * 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) {        //只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表        ListNode* cur = head;        ListNode* pre = NULL; //反转后的头节点        ListNode* tmp; //用于存放cur->next        while(cur)        {            tmp = cur->next; //存放节点原来的next            cur->next = pre; //改变指向            //pre cur都进行后移            pre = cur;            cur = tmp;        }        //注意pre现在才是我们的头节点,不能再返回head了        return pre;    }};

    总结:

    链表问题很有意思,指针的指向也非常灵活,也要记得保存可能会丢失的那个值,很常见的就是cur->next。

上一篇:怎么看服务器公网地址?

下一篇:手机怎么修改网址的域名