LeetCode //C - 82. Remove Duplicates from Sorted List II

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 82. Remove Duplicates from Sorted List II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

82. Remove Duplicates from Sorted List II

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

Example 1:

LeetCode //C - 82. Remove Duplicates from Sorted List II,LeetCode,leetcode,c语言,算法

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

LeetCode //C - 82. Remove Duplicates from Sorted List II,LeetCode,leetcode,c语言,算法

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:
  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

From: LeetCode
Link: 82. Remove Duplicates from Sorted List II


Solution:

Ideas:

1. Initialize Pointers and Dummy Node:

  • Create a dummy node that acts as a placeholder for the new list. Initialize prev to this dummy node and curr to the head of the original list.

2. Traverse the Original List:

  • Go through each node in the list using the curr pointer.

3. Check for Duplicates:

  • If the curr node has a duplicate (i.e., curr->val is the same as curr->next->val), move curr to the last duplicate node. This is done using the while loop within the main while loop.

4. Add Unique Nodes to New List:

  • If the curr node is not a duplicate, add it to the new list. The prev pointer keeps track of the last node added to the new list.

5. Move to Next Node:

  • Move curr to the next node in the original list.

6. Terminate New List:

  • Make sure to set the next of the last node in the new list to NULL.

7. Return New List:文章来源地址https://www.toymoban.com/news/detail-693751.html

  • The new list starts after the dummy node. So, we return dummy->next as the new head of the list.
Code:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    // Create a dummy node to serve as the head of the new list
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->val = 0;
    dummy->next = NULL;
    
    // Initialize pointers
    struct ListNode* prev = dummy;
    struct ListNode* curr = head;
    
    while (curr != NULL) {
        // Check if the current node is a duplicate
        int duplicate = 0;
        while (curr->next != NULL && curr->val == curr->next->val) {
            duplicate = 1;
            curr = curr->next;
        }
        
        // If it's not a duplicate, add it to the new list
        if (duplicate == 0) {
            prev->next = curr;
            prev = curr;
        }
        
        // Move to the next node in the original list
        curr = curr->next;
    }
    
    // Terminate the new list
    prev->next = NULL;
    
    // Return the new list (skipping the dummy node)
    struct ListNode* newHead = dummy->next;
    free(dummy);
    return newHead;
}

到了这里,关于LeetCode //C - 82. Remove Duplicates from Sorted List II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【每日一题】Leetcode - 19. Remove Nth Node From End of List

    Leetcode - 19. Remove Nth Node From End of List Drawing on the method of finding midpoints in linked lists, use quick slow pointer Finding midpoints in linked lists nothing

    2024年02月12日
    浏览(50)
  • LeetCode //167. Two Sum II - Input Array Is Sorted

    Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 = index1 index2 numbers.length. Return the indices of the two numbers, index1 and index2 , added by one as an integer array [index1

    2024年02月15日
    浏览(51)
  • LeetCode——82. 删除排序链表中的重复元素II

    通过万岁!!! 题目:题目的大致意思就是,给你一个升序的链表,然后让你里面的元素有重复的,所有重复的元素都进行一个删除。 思路:这个题的简化版是“83.删除排序链表中的重复元素”。看到链表的题目可以优先考虑一下双指针。这里因为head也有可能跟下面的重复

    2024年01月16日
    浏览(46)
  • LeetCode - #82 删除排序链表中的重复元素 II

    我们社区陆续会将顾毅( Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。 )的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 LeetCode 算法到目前我们已经更新了 82 期,我们会保持更新时间和进度( 周一、周三、周五早上 9:00 发布 ),每期的内容不多,

    2024年02月10日
    浏览(35)
  • ​LeetCode解法汇总82. 删除排序链表中的重复元素 II

    https://github.com/September26/java-algorithms 给定一个已排序的链表的头  head  ,  删除原始链表中所有重复数字的节点,只留下不同的数字  。返回  已排序的链表  。 示例 1: 示例 2: 提示: 链表中节点数目在范围  [0, 300]  内 -100 = Node.val = 100 题目数据保证链表已经按升序  排

    2024年01月17日
    浏览(44)
  • 【LeetCode刷题-链表】--82.删除排序链表中的重复元素II

    由于链表是排好序的,所以只需要对其进行一次遍历即可,比较相邻节点对应的值

    2024年02月06日
    浏览(39)
  • leetcode做题笔记82删除排序链表中的重复元素 II

    给定一个已排序的链表的头  head  ,  删除原始链表中所有重复数字的节点,只留下不同的数字  。返回  已排序的链表  。 本题将重复的元素全部删除,可以考虑新建一个链表,若有重复元素则不放入新链表中,最后输出新链表即可。链表操作需要用另一个链表记录原来

    2024年02月12日
    浏览(58)
  • 算法leetcode|82. 删除排序链表中的重复元素 II(rust重拳出击)

    给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 链表中节点数目在范围 [0, 300] 内 -100 = Node.val = 100 题目数据保证链表已经按升序 排列 面对这道算法题目,二当家的再次陷入了沉思。 这道题目和 83. 删除排序

    2024年02月08日
    浏览(36)
  • 算法: 移除单链表的倒数第N个节点 19. Remove Nth Node From End of List

    Given the head of a linked list, remove the nth node from the end of the list and return its head. Example 1: Example 2: Example 3: Constraints: The number of nodes in the list is sz. 1 = sz = 30 0 = Node.val = 100 1 = n = sz Follow up: Could you do this in one pass? 该方法采用了两次遍历链表的方法。首先,它计算链表的总长度,然后通

    2024年02月13日
    浏览(46)
  • 【LeetCode 算法】Linked List Cycle II 环形链表 II

    给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从

    2024年02月14日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包