当前位置: 代码迷 >> 综合 >> leetcode82. Remove Duplicates from Sorted List Ⅱ(删除有序链表中的重复数字,只保留非重复数字)
  详细解决方案

leetcode82. Remove Duplicates from Sorted List Ⅱ(删除有序链表中的重复数字,只保留非重复数字)

热度:65   发布时间:2023-11-17 01:23:22.0

题目要求

给定一个有序链表,删除所有的重复数字,仅仅留下非重复数字。
注意:和题目
leetcode83. Remove Duplicates from Sorted List(删除有序链表中的重复项)的区别。

示例

//Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5 // 删掉重复的数字3,4//Example 2:
Input: 1->1->1->2->3
Output: 2->3 // 删掉重复的数字1

解题思路

本题目最大的难点即和83题的不同就是,需要把所有的重复都删除,如:EX1中删除重复的3,4(且不保留任意一个3,4).在83题中,我们通过
p->next = p->next->next 可以通过去除重复数字的后一个数,达到去除相邻元素重复的目的。但是同时却不能去除前一个重复数字。这是本题目中所不允许的。

因为要全部删除重复的数字,所以我们想到可以通过记录重复数字的前驱结点,以及重复数字的值,来循环的进行删除节点。还通过这个公式进行删除,
p->next = p->next->next 但是比较的不是当前遍历元素的值和下一个元素的值。而是当前元素后两个值之间的关系,这样就可以把当前元素作为一个前驱结点进行看待 然后再进行一个循环删除的操作,当前元素后边所有重复的点都删除,直到遇到非重复数字,进行后移。

过程说明

1-2-3-3-4-4-5 为例子,来说明思路的实现流程,当遍历到2的时候,发现他的后两个元素都是3,此时首先记下重复元素是3,然后进行删除第一个3。

这时链表变成1-2-3-4-4-5,回到2,判断他的下一个数字是3(是记录的重复元素),所以再删掉。

此时链表变成1-2-4-4-5,然后回到2,发现他的后两个元素是4,然后进行和上面一样的操作,连续删除两个4.

这时候链表变成1-2-5,因不符合循环的条件而返回。

主要代码c++

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
    
public:ListNode* deleteDuplicates(ListNode* head) {
      ListNode *dummpy = new ListNode(0); // 建造傀儡节点dummpy->next = head;ListNode *p = dummpy;int dup; while(p->next && p->next->next){
    if(p->next->val == p->next->next->val)// 有重复{
    dup = p->next->val; //记录重复的数值while(p->next&&p->next->val == dup)//下一点是重复值那么删掉p->next = p->next->next;}else{
    p = p->next; //下一节点不是重复点那么,向后移动}}      return dummpy->next;        }
};

原题链接 :https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

  相关解决方案