写点什么

算法题学习 --- 删除有序链表中重复的元素 -I

作者:桑榆
  • 2022-11-20
    广东
  • 本文字数:892 字

    阅读完需:约 3 分钟

题目

描述

删除给出链表中的重复元素(链表中元素从小到大有序),使链表中的所有元素都只出现一次例如:给出的链表为 1→1→2,返回 1→2.给出的链表为 1→1→2→3→3,返回 1→2→3.

数据范围:链表长度满足 0≤n≤100,链表中任意节点的值满足∣val∣≤100

进阶:空间复杂度 O(1),时间复杂度 O(n)

示例 1

输入:{1,1,2}返回值:{1,2}
复制代码

示例 2

输入:{}返回值:{}
复制代码

分析

分析特殊情况

不难看出,在链表为空和链表只有一个元素时,只需要返回输入的链表头即可。

分析一般情况

由于需要删除相同的元素,那么我们就保留遇到的第一个元素即可,因为链表只能顺序访问,不能够逆序访问,如果发现后面的元素的值与它相等,那么就删除新元素,指向再下一个元素,继续判断;如果不等,说明可以继续往后遍历。

基于这样的想法,我们可以设定两个指针一个指向之前的元素 pPre,初始化为头结点,pCur 为当前遍历的元素,遍历链表直到 pCur 为空指针。

  • 当 pPre 的元素值与 pCur 的元素值相等时,两者均往后移;

  • 当 pPre 的元素值与 pCur 的元素值不等时,删除 pCur 指向的元素,并更新 pCur 为下一个元素,将 pPre 的指针执向 pCur。

代码示例

如分析所述,需要注意的是,这里对节点进行删除时,需要事先分配一个临时变量存储需要释放的指针。

/** * struct ListNode { *  int val; *  struct ListNode *next; * }; */
class Solution {public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here if(nullptr == head || nullptr == head->next){ return head; }
ListNode *pPre = head; ListNode *pCur = head->next; while(nullptr != pCur){ if(pPre->val != pCur->val){ pPre = pCur; pCur = pCur->next; }else{ ListNode *pTemp = pCur; pCur = pCur->next; delete pTemp; pPre->next = pCur; } } return head; }};
复制代码


发布于: 刚刚阅读数: 4
用户头像

桑榆

关注

北海虽赊,扶摇可接;东隅已逝,桑榆非晚! 2020-02-29 加入

Android手机厂商-相机软件系统工程师 爬山/徒步/Coding

评论

发布
暂无评论
算法题学习---删除有序链表中重复的元素-I_算法题_桑榆_InfoQ写作社区