[LeetCode]82.Remove Duplicates from Sorted List II

简介:

【题目】

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

【题意】

给定一个有序链表,删除具有重复的数字,从原来的列表中只留下了不同数字的所有节点。

【分析】

思路1:

遍历链表,记录重复元素的起始位置和截止位置。要删除的重复元素的上一个位置begin,截止位置end。例如:1,2,2,2,4 begin = 0 end = 3

如果当前元素和上一个元素相等,则更新end;如果不相等则判断beigin和end是否相等,相等没有重复元素需要删除,不相等删除[being+1,end]中元素。

如果最后几个元素重复,则需要最后单独通过判断begin,end是否等来解决。

【代码1】

/*********************************
*   日期:2014-01-28
*   作者:SJF0115
*   题号: Remove Duplicates from Sorted List II
*   来源:http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        //添加虚拟头结点
        ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
        dummy->next = head;
        //记录上一节点的值
        int preVal = head->val;
        ListNode *pre = head,*cur = head->next;
        //begin 要删除节点的上一节点  end 要删除的最后节点
        ListNode *begin = dummy,*end = dummy;
        while(cur != NULL){
            if(cur->val == preVal){
                //如果当前元素和上一个元素相等则更新删除截至元素
                end = cur;
            }
            else{
                preVal = cur->val;
                //[begin,end]有重复元素
                if(begin != end){
                    //删除重复元素
                    begin->next = end->next;
                    end = begin;
                }
                //[begin,end]没有重复元素,更新删除起始元素
                else{
                    begin = end = pre;
                }
            }
            pre = cur;
            cur = cur->next;
        }
        //如果最后几个元素相等例如:2,1,1,1,1
        if(begin != end){
            //删除重复元素
            begin->next = end->next;
        }
        return dummy->next;
    }
};
int main() {
    Solution solution;
    int A[] = {2,1,1,1,1,1};
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *node;
    ListNode *pre = head;
    for(int i = 0;i < 6;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }
    head = solution.deleteDuplicates(head->next);
    while(head != NULL){
        printf("%d ",head->val);
        head = head->next;
    }
    return 0;
}


【代码2】

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
        dummy->next = head;

        ListNode *pre = dummy,*cur = head;
        while (cur != NULL) {
            int preVal = cur->val;
            if (cur->next && cur->next->val == preVal) {
                while (cur && cur->val == preVal) {
                    pre->next = cur->next;
                    delete cur;
                    cur = pre->next;
                }
                cur = pre;
            }
            pre = cur;
            cur = cur->next;
        }
        return dummy->next;
    }
};

【代码3】

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *dummy = (ListNode*)malloc(sizeof(ListNode));
        dummy->next = head;

        ListNode *pre = dummy,*cur = head;
        ListNode *temp;
        int i = 0;
        while (cur != NULL) {
            //判断是否有重复元素
            bool duplicated = false;
            //寻找重复元素删除
            while(cur->next != NULL && (cur->val == cur->next->val)){
                duplicated = true;
                temp = cur->next;
                //删除cur元素
                pre->next = cur->next;
                cur = temp;
            }//while
            //删除重复元素的最后一个
            if(duplicated){
                temp = cur->next;
                //删除重复元素的最后一个
                pre->next = cur->next;
                cur = temp;
                continue;
            }//if
            pre = cur;
            cur = cur->next;
        }//while
        return dummy->next;
    }
};


目录
相关文章
|
Java
Leetcode 114. Flatten Binary Tree to Linked List
思路也很简单,先把root的左子树(如有)变成单链表 leftlinkedlist,把root的右子树(如有)变成单链表 rightlinkedlist,再把root的右节点变成leftlikedlist,再把rightlinkedlist接到leftlinkedlist后面,代码如下。
49 1
Leetcode 19.Remove Nth Node From End of List
删除单链表中的倒数第n个节点,链表中删除节点很简单,但这道题你得先知道要删除哪个节点。在我的解法中,我先采用计数的方式来确定删除第几个节点。另外我在头节点之前额外加了一个节点,这样是为了把删除头节点的特殊情况转换为一般情况,代码如下。
42 0
|
2月前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
29 3
|
4月前
|
存储 NoSQL 算法
Redis6入门到实战------ 三、常用五大数据类型(列表(List)、集合(Set)、哈希(Hash)、Zset(sorted set))
这是关于Redis 6入门到实战的文章,具体内容涉及Redis的五大数据类型:列表(List)、集合(Set)、哈希(Hash)、有序集合(Zset(sorted set))。文章详细介绍了这些数据类型的特点、常用命令以及它们背后的数据结构。如果您有任何关于Redis的具体问题或需要进一步的帮助,请随时告诉我。
|
7月前
使用List中的remove方法遇到数组越界
使用List中的remove方法遇到数组越界
108 2
|
7月前
List中的remove方法遇到报错不能删除以及四种解决办法点赞收藏
List中的remove方法遇到报错不能删除以及四种解决办法点赞收藏
270 0
|
7月前
|
大数据 Java 程序员
「LeetCode合集」链表(List)及经典问题
「LeetCode合集」链表(List)及经典问题
55 0
避免list中remove导致ConcurrentModificationException
避免list中remove导致ConcurrentModificationException
52 0
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
41 0
|
6月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
1039 1