daily leetcode - remove-duplicates-from-sorted-list - !

题目地址

https://leetcode.com/problems/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;
    }
};

本文参考自:
https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode


标题: daily leetcode - remove-duplicates-from-sorted-list - !
文章作者: lonuslan
文章链接: https://www.lonuslan.com/articles/2020/02/29/1582951354842.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hi I'm LonusLan
    评论
    0 评论
avatar

取消