专栏首页光城(guangcity)精益求精解LeetCode(82与83)

精益求精解LeetCode(82与83)

好久没有刷题与更文了,今天来一场LeetCode上面简单与中等题目多种方法刷题。

1.题目

83. 删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2输出: 1->2示例 2:

输入: 1->1->2->3->3输出: 1->2->3

2.思想

(1)使用快慢指针

特殊情况判断:链表为空或链表只有一个节点,直接返回。

设p=head,q=head->next,让不断去移动,直到q的val不等于p的val,那么将p连接上q即可。

循环特殊情况判断,当快指针指向为空,直接让p指向NULL,break掉函数,返回即可。

分析:时间复杂度为O(n),空间复杂度为O(1)。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        ListNode *p=head,*q=p->next;
        while(p) {
            if(p->val!=q->val) {
                p->next=q;
                p=q;
            }
            q=q->next;
            if(q==NULL){
                p->next=NULL;
                break;
            }
        }
        return head;
    }
};

(2)递归

递归终止条件:无节点或只有一个节点。

递归到最后,例如尾部节点为2 2,也就是当head->next指向末尾的2时候,此时需要判断head与head->next值是否相等,如果相等,直接让head指向尾部,依次覆盖所有重复节点。否则,直接让head指向尾部节点。

分析:时间复杂度为O(n),空间复杂度为O(1)。

ListNode* deleteDuplicates(ListNode* head) {
    //链表是否为空或者是否到末尾
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *p = deleteDuplicates(head->next);
    if (head->val == head->next->val)
        head = p;
    else
        head->next = p;
    return head;
}

2.题目

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5输出: 1->2->5示例 2:

输入: 1->1->1->2->3输出: 2->3

3.思想

3.1方法一

这道题与上述题目很相似,于是采用上述题目思想完成。

上述思想中核心就是快慢指针,快指针q,满指针p,每次q指向的是新元素,也就是满足p->val!=q->val,就需要判断当前链表是否值不同连续

值不同连续判断就是p->next==q,(两者距离只差1)。如果满足,说明当前p指向的元素无重复,那么直接让r(此指针为新返回链表的遍历指针)指针指向p指向的节点(注意这里是创建了一个p->val相同的节点),r指针再指向下一个节点,q指针处理是不作为循环的遍历指针,每次++。

到最后,q指针为空,分为两种情况:

(1)值不同不连续: 例如:[1,2,2] p指向了2,q指向了NULL,此时需要将r->next指针直接指向末尾的NULL*

(2)值不同连续: 例如:[1,2,2,5] p指向了5,q指向了NULL,此时需要连接p,即r->next=p

ListNode* deleteDuplicates(ListNode* head) {
    if(head==NULL || head->next==NULL) return head;

    ListNode* p=head,*q=p->next;
    ListNode* HEAD=new ListNode(0),*r=HEAD;

    while(q) {
        cout<<p->val<<" "<<q->val<<endl;

        if(p->val!=q->val) {
            if(p->next==q) {
                r->next=new ListNode(p->val);
                r=r->next;
            }

            p=q;
        }
        cout<<r->val<<endl;
        q=q->next;
    }
    if(p->next!=q)
        r->next=NULL;
    else
        r->next=new ListNode(p->val);
    r=HEAD->next;
    delete HEAD;
    return r;
}

分析:*时间复杂度:O(n),空间复杂度:O(n)。

那能否优化空间复杂度为O(1)呢?

我们继续优化。

3.2方法二

上述的空间复杂度耗费在每次都要去创建新的节点,那么我们不创建不就行了,只需要拓展一个指针,让该指针不断动态修改链表。

ListNode* deleteDuplicates(ListNode* head) {
    // 无节点或者只有一个节点情况
    if(head==NULL || head->next==NULL) return head;

    // p跳跃指向不同节点,q遍历所有节点,r动态修改链表
    ListNode* p=head,*q=p->next,*r=p;
    // 针对 [1 1 2] 这种情况需要先确定返回链表头结点,那么这里创建一个头结点,让上述定义的r指针取动态的修改返回链表。
    ListNode* HEAD=new ListNode(0); // 返回链表的头指针

    while(q) {
        /**
         * 值不同
         */
        if(p->val!=q->val) {
            /**
             * 值不同且连续
             */
            if(p->next==q) {
                /**
                 * 返回链表是否有开始节点
                 */
                if (HEAD->next == NULL) {
                    r = p;
                    HEAD->next = r;
                } else {
                    r->next = p;
                    r = p;
                }
            }
            // p指向新值
            p=q;
        }
        q=q->next;  //遍历链表
    }
    if(p->next!=q)
        r->next=NULL;
    else {
        if(HEAD->next==NULL)
            HEAD->next=p;
        else
            r->next=p;
    }
    r=HEAD->next;
    delete HEAD;
    return r;
}

到最后,q指针为空,分为两种情况:

(1)值不同不连续

例如:[1,2,2] p指向了2,q指向了NULL,此时需要将r->next指针直接指向末尾的NULL

(2)值不同连续

  • 值不同连续,且返回链表的没有开始节点,也就是HEAD->next=NULL 例如:[1,1,2] p指向了2,q指向了NULL,此时需要连接p,但是Head->next为空,直接让HEAD->next指向p即可
  • 值不同连续,且回链表的有开始节。 例如:[1,2,2,5] p指向了5,q指向了NULL,此时需要连接p,即r->next=p

分析:时间复杂度:O(n),空间复杂度O(1)。

到此为止,自己实现的思路全部写完,后面是看题解与评论上的一些思路,并对他们的代码做了一些优化后呈现出来的。

3.3 方法三

第82题用到了递归法,这道题也可以!

思想就是如果当前节点与后一节点相同,那么递归后一节点,直到找到不同的节点,并让前一节点(对应前面提到的当前节点)指向后一节点,依次递归下去,如果递归过程中当前节点与后一节点不同,直接链接,最后的head就是最终结果。

ListNode* deleteDuplicates2(ListNode* head) {
    if(head==NULL || head->next==NULL) return head;

    ListNode *p = head->next;

    if(head->val == p->val) {
        while (p&&head->val==p->val){
            p=p->next;
        }
        head=deleteDuplicates2(p);
    } else {
        head->next=deleteDuplicates2(p);
    }
    return head;
}

时间复杂度O(n),空间复杂度O(1)。

3.4 方法四

这个方法比较传统,在题解中空间复杂度为O(n),这里我将其进行优化,最终的时间复杂度为O(n),空间复杂度为O(1)。

思想是使用快慢指针,用慢指针跳过那些重复数,慢指针指的的元素就是返回链表中的元素。

ListNode* deleteDuplicates3(ListNode* head) {
    if(head==NULL || head->next==NULL) return head;
    // 1 1 2 2 3
    ListNode *p=head,*q=p->next,*pre=head;
    // 确定返回节点的头在哪里!
    bool isonce=true;
    while(p) {
        if(q&&p->val==q->val) {
            int tmp = p->val;
            while(p&&p->val==tmp)
                p=p->next;
            if(p) q=p->next;
        } else {
            // 1 2 3   1 1 2 3
            if (isonce) {
                head = p;
                isonce = false;
                pre = head;
            } else{
                pre->next = p;
                pre = p;
            }
            p=q;
            if(q)
                q=q->next;
        }
    }
    if(isonce) {
        head=NULL;
        isonce=false;
    } else {
        pre->next=p;
    }

    return head;
}

今日刷题完毕,好久没有刷题了,累了,休息,闪了,欢迎大家转发,收藏,点赞!

本文分享自微信公众号 - 光城(guangcity),作者:lightcity

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ​精益求精单链表归并排序与快速排序

    本节主要阐述自顶向下与自底向上的归并排序,以及改变连接状态与改变节点值的可快速排序。下面来仔细阐述。

    公众号guangcity
  • 一道题看快排

    今天除了早上没课,一天的满课,但是我仍然坚持发文了,仍然坚持做题了,你们吗?算法最优群各位同学加油啦!!!看最后有哪些坚持下来的!

    公众号guangcity
  • LeetCode之链表(10)

    今天有点闲,就来连刷几道题,下次不这样干了,有点hold不住,建议以后保持平衡刷题规律!

    公众号guangcity
  • 程序员面试金典 - 面试题 02.06. 回文链表(快慢指针+链表反转)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/palindrome-linked-list-lcci...

    Michael阿明
  • Leetcode 82 Remove Duplicates from Sorted List II

    Given a sorted linked list, delete all nodes that have duplicate numbers, leavi...

    triplebee
  • leetcode 83 Remove Duplicates from Sorted List

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

    流川疯
  • 两两交换链表中的节点

    一份执着✘
  • 链表问题(二)-LeetCode 147、876、234、817、92(链表的中点,快慢指针)

    首先判断两个相邻节点的大小,如果head->val > head->next->val,则需要将head->next->val插入到从dummy节点开始遍历第一...

    算法工程师之路
  • LintCode 删除排序链表中的重复数字 II题目分析代码

    给定一个排序链表,删除所有重复的元素只留下原链表中没有重复的元素。 样例 给出 1->2->3->3->4->4->5->null,返回 1->2->5->...

    desperate633
  • 问题系列之Java中删除有序List的重复数据——提供两种方法

    Java学习网(www.javalearns.com)提拱 现在给出一个有序的List,删除其中重复的元素,要求第个元素只能出现一次,并且是经过的排序的; ...

    用户1289394

扫码关注云+社区

领取腾讯云代金券