代码随想录-链表1( 203.移除链表元素、)

这篇具有很好参考价值的文章主要介绍了代码随想录-链表1( 203.移除链表元素、)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

203. 移除链表元素

/**
 * 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 != nullptr && head->val == val)
        {
            head = head->next;
        }
        ListNode* node = head;
        
        while (node != nullptr && node->next != nullptr)
        {
            if (node->next->val == val)
            {
                node->next = node->next->next;
            }
            else 
            {
                node = node->next;
            }
        }
        return head;
    }
};

707. 设计链表

class MyLinkedList {
public:
    struct linknode 
    {
        int val;
        linknode* next;
        linknode(int x): val(x), next(NULL){}
    };


    MyLinkedList() 
    {
        this->head = new linknode(0);
        this->size = 0;
    }
    
    int get(int index) 
    {
        linknode* cur = this->head;
        if (this->size == 0) return -1;
        else if (index > this->size-1) return -1;
        else 
        {
            for (int i=0; i<index; i++)
            {
                cur = cur->next;
            }
        }
        return cur->val;
    }
    
    void addAtHead(int val) 
    {
        if (this->size == 0)
        {
            this->head->val = val;
            this->size = 1;
        }
        else
        {
            linknode* cur = new linknode(val);
            linknode* tmp = this->head;
            this->head = cur;
            cur->next = tmp;
            this->size += 1; 
        }
    }
    
    void addAtTail(int val) 
    {
        if (this->size == 0)
        {
            this->head->val = val;
            this->size = 1;
        }
        else
        {
            linknode* cur = new linknode(val);
            linknode* tmp = this->head;
            while (tmp->next != NULL)
            {
                tmp = tmp->next;
            }
            tmp->next = cur;
            this->size++;
        }



    }
    
    void addAtIndex(int index, int val) 
    {
        if (index > this->size) return;
        else if (index == this->size) addAtTail(val);
        else if (index == 0) addAtHead(val);
        else
        {
            linknode* cur = this->head;
            linknode* newnode = new linknode(val);
            for (int i=0; i<index-1; i++)
            {
                cur = cur->next;
            }
            linknode* tmp = cur->next;
            cur->next = newnode;
            newnode->next = tmp;
            this->size++;
        }


    }
    
    void deleteAtIndex(int index) 
    {
        if (this->size == 0) return;
        else if (index > this->size-1) return;
        else{
            if (index == 0) this->head = this->head->next;
            else if (index == this->size-1) 
            {
                linknode* cur = this->head;
                while (cur != NULL && cur->next != NULL && cur->next->next != NULL)
                {
                    cur = cur->next;
                }
                cur->next = NULL;
            }
            else
            {
                linknode* cur = this->head;
                for (int i=0; i<index-1; i++)
                {
                    cur = cur->next;
                }
                cur->next = cur->next->next;
            }
            this->size--;
        }

    }

private:
    linknode *head;
    int size;

};

/**
 * 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. 反转链表

        自己写的是从后往前去反转,没想到可以从前往后反转的方法,以为地址不连续并且无法根据索引找地址就没办法做,看了双指针方法后才发现如何从前往后反转,其实只要记录每个结点的地址就可以了,还是对链表的概念把握的不好,需要多刷题。

自己做的:

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (head==nullptr) return head;
        if (head->next==nullptr) return head;
        ListNode* newnode = head;
        ListNode* tmp1 = head;
        // while (newnode != nullptr && newnode->next != nullptr && newnode->next->next != nullptr)
        // {
        //     newnode = newnode->next;
        // }
        // ListNode*
        int flag = 0;

        while (head->next != nullptr)
        {
            ListNode* cur = head;
            while (cur != nullptr && cur->next != nullptr && cur->next->next != nullptr)
            {
                cur = cur->next;
            }
            if (flag == 0)
            {
                newnode = cur->next;
                tmp1 = cur->next;
                cur->next = nullptr;
            }
            else
            {
                ListNode* tmp = cur->next;
                cur->next = nullptr;
                tmp1->next = tmp;
                tmp1 = tmp;
            }
            flag++;
        }
        tmp1->next = head;
        return newnode;

    }
};

双指针:文章来源地址https://www.toymoban.com/news/detail-826335.html

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点,因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

到了这里,关于代码随想录-链表1( 203.移除链表元素、)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【代码随想录刷题记录】 203.移除链表元素 、 707.设计链表 、206.反转链表

    题目 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 题目链接:https://leetcode.cn/problems/remove-linked-list-elements/ 代码 小结 该题主要注意链表删除的操作以及在特殊情况下如何进行操作。特殊情况包括头结点为目标

    2024年02月08日
    浏览(47)
  • 代码随想录Day3|链表理论基础|203.移除链表元素|707.设计链表|206.反转链表

    虽然以前写过一次链表,但是真的已经忘得一干二净了 链表 :通过 指针 串联在一起的线性结构,每个 节点 都由数据域和指针域组成。 指针域 :存放下一个节点的指针,最后一个节点的指针域指向null,也即空指针 head :链表的入口节点,也即链表的头节点 链表的类型 单

    2024年02月11日
    浏览(54)
  • 代码随想录第三天|链表理论基础,LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表

    链表: 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是head。 链表类型: 1.单链表 单链表中的指

    2024年02月11日
    浏览(53)
  • 代码随想录day3|链表理论基础、移除链表元素、设计链表、翻转链表

    1、基本类型:单链表、双链表、循环链表 2、存储方式:和数组不一样,链表是随机存储在内存中,不是连续分配在内存中。 3、链表的定义: 定义了一个数据域,还有一个指针域,并且定义了一个构造函数。 4、链表的操作: 删除节点:  在图中,若需要删除D这个节点,只

    2024年02月05日
    浏览(46)
  • 代码随想录Day3 | 链表01-leetcode203、707、206

    题目链接:移除链表元素 思路: 链表中元素的添加和删除关键是要 保证不断链且指向关系正确 。对于删除操作,链的修改涉及将待删除元素的前一个元素指向待删除元素的后一个元素,因此在判断当前元素是否需要删除时,要记录当前元素的前后指针。 1.删除头结点时另作

    2024年02月16日
    浏览(68)
  • 【代码随想录-Leetcode第二题:27.移除元素】

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的 样例:示例 1: 解释:函数

    2024年02月14日
    浏览(51)
  • 代码随想录day1 | 704.二分查找 27.移除元素

    1、循环变量 2、判断条件 当时左闭右闭时,while循环里面的条件,我们可以先假设,有等号即有left=right的情况,例如[1,1]这个区间,那么循环是要进入里面的,所以要取得等号。 判断的时候,nums[mid]tar,那么必然tar不在右半区间,所以right=mid-1 nums[mid]tar,那么必然tar不在左半

    2024年02月15日
    浏览(61)
  • 【代码随想录算法第一天| 704.二分查找 27.移除元素】

    题目链接:二分查找 文章讲解:代码随想录.二分查找 视频讲解:手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili 二分前提:有序数组,数组中无重复元素 方法:结合数组的特征,可以为左闭右闭区间[0, 数组长度-1],或者左

    2024年02月16日
    浏览(45)
  • 代码随想录第一天 | LeetCode704.二分查找,LeetCode 27.移除元素

    数组理论基础要点: 数组也是数据结构的一种, 是存放在连续内存空间上的相同类型数据的集合。 数组注意点: 数组下标都是从0开始的。 数组内存空间的地址是连续的。 因为上述两点, 数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要

    2024年02月08日
    浏览(50)
  • 203.移除链表元素

    循环遍历整个链表 定义两个指针:prev,cur 如果cur是要删除的节点,prev-cur-next,然后free(cur) 但是注意每次都要新定义一个节点del,用来free,不影响原来的cur节点往下循环 更新cur和prev 但是需要注意如果删除的是头节点,就要特殊处理,画图带上指针,情况分析,一目了然。

    2024年01月22日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包