文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++中怎么利用LeetCode移除有序链表中的重复项

2023-06-20 16:05

关注

C++中怎么利用LeetCode移除有序链表中的重复项,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。

[LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

这道题让我们移除给定有序链表的重复项,那么可以遍历这个链表,每个结点和其后面的结点比较,如果结点值相同了,只要将前面结点的 next 指针跳过紧挨着的相同值的结点,指向后面一个结点。这样遍历下来,所有重复的结点都会被跳过,留下的链表就是没有重复项的了,代码如下:

解法一:

class Solution {public:    ListNode* deleteDuplicates(ListNode* head) {        ListNode *cur = head;        while (cur && cur->next) {            if (cur->val == cur->next->val) {                cur->next = cur->next->next;            } else {                cur = cur->next;            }        }        return head;    }};

我们也可以使用递归的方法来做,首先判断是否至少有两个结点,若不是的话,直接返回 head。否则对 head->next 调用递归函数,并赋值给 head->next。这里可能比较晕,先看后面一句,返回的时候,head 结点先跟其身后的结点进行比较,如果值相同,那么返回后面的一个结点,当前的 head 结点就被跳过了,而如果不同的话,还是返回 head 结点。可以发现了,进行实质上的删除操作是在最后一句进行了,再来看第二句,对 head 后面的结点调用递归函数,那么就应该 suppose 返回来的链表就已经没有重复项了,此时接到 head 结点后面,在第三句的时候再来检查一下 head 是否又 duplicate 了,实际上递归一直走到了末尾结点,再不断的回溯回来,进行删除重复结点,参见代码如下:

解法二:

class Solution {public:    ListNode* deleteDuplicates(ListNode* head) {        if (!head || !head->next) return head;        head->next = deleteDuplicates(head->next);        return (head->val == head->next->val) ? head->next : head;    }};

看完上述内容,你们掌握C++中怎么利用LeetCode移除有序链表中的重复项的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注编程网行业资讯频道,感谢各位的阅读!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯