C++实现LeetCode(83.移除有序链表中的重复项)

[LeetCode] 83. 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;
    }
};

到此这篇关于C++实现LeetCode(83.移除有序链表中的重复项)的文章就介绍到这了,更多相关C++实现移除有序链表中的重复项内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(19.移除链表倒数第N个节点)

    C++实现LeetCode(19.移除链表倒数第N个节点)

    [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the en

  • C++实现LeetCode(18.四数之和)

    [LeetCode] 18. 4Sum 四数之和 Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be

  • C++实现LeetCode(20.验证括号)

    [LeetCode] 20. Valid Parentheses 验证括号 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open

  • C++实现LeetCode(21.混合插入有序链表)

    [LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2

  • C++实现LeetCode(17.电话号码的字母组合)

    [LeetCode] 17. Letter Combinations of a Phone Number 电话号码的字母组合 Given a string containing digits from 2-9inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone butt

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

  • C++实现LeetCode(88.混合插入有序数组)

    [LeetCode] 88. Merge Sorted Array 混合插入有序数组 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1and nums2 are m and n respectively. You may assume that nums1 has

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. 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-

  • C++实现LeetCode(82.移除有序链表中的重复项之二)

    [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. Example 1: Input: 1->2->3->3->4->4->5 Outp

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

  • java算法入门之有效的括号删除有序数组中的重复项实现strStr

    java算法入门之有效的括号删除有序数组中的重复项实现strStr

    目录 1.LeetCode 20.有效的括号 题目 小编菜解 思路及算法 大神解法 2.LeetCode 26.删除有序数组中的重复项 题目 小编菜解初版 小编菜解改进版 思路及算法 大神解法 3.LeetCode 28.实现strStr 题目 小编菜解 大神解法 也许,我们永远都不会知道自己能走到何方,遇见何人,最后会变成什么样的人,但一定要记住,能让自己登高的,永远不是别人的肩膀,而是挑灯夜战的自己,人生的道路刚刚启程,当你累了倦了也不要迷茫,回头看一看,你早已不再是那个年少轻狂的少年. 1

  • JavaScript删除有序数组中的重复项

    JavaScript删除有序数组中的重复项

    目录 如果有一个有序数组 nums ,要求原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度. 不要使用额外的数组空间,必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成. 说明: 为什么返回数值是整数,但输出的答案是数组呢? 注意:输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的. 你可以想象内部操作如下: // nums 是以"引用"方式传递的.也就是说,不对实参做任何拷贝 int len = removeDu

  • C语言 详解如何删除有序数组中的重复项

    C语言 详解如何删除有序数组中的重复项

    目录 删除有序数组中的重复项Ⅰ a.思路 b.图解 c.代码 d.思考 删除有序数组中的重复项Ⅱ a.思路 b.图解 c.代码 d.思考 删除有序数组中的重复项Ⅰ a.思路 定义变量 int dest=0,cur=1,nums[cur]与nums[dest]逐一比较. nums[cur]!=nums[dest],将nums[cur]放入dest下一个位置,更新dest. nums[cur]!=nums[dest],cur移动. cur==numsSize,结束.返回dest+1. b.图解 c.

  • C++实现LeetCode(81.在旋转有序数组中搜索之二)

    [LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]). You are given a target value to search.

  • C++实现LeetCode(33.在旋转有序数组中搜索)

    [LeetCode] 33. Search in Rotated Sorted Array 在旋转有序数组中搜索 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If f

随机推荐