【力扣】83. 删除排序链表中的重复元素、82. 删除排序链表中的重复元素Ⅱ

简介: 【力扣】83. 删除排序链表中的重复元素、82. 删除排序链表中的重复元素Ⅱ

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

题目描述

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

示例 1:


输入:head = [1,1,2]

输出:[1,2]

示例 2:



输入:head = [1,1,2,3,3]

输出:[1,2,3]

提示:

  • 链表中节点数目在范围 [0, 300]
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

解题方案

  • C 遍历链表,只需比较当前节点和下一个节点的值
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    struct ListNode* temp = head;
    if (head == NULL)
        return head;
    while (temp && temp->next) {
        if (temp->val == temp->next->val) {
            temp->next = temp->next->next;
        } else {
            temp = temp->next;
        }
    }
    return head;
}


  • C 递归实现
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {

    if (head == NULL || head->next == NULL)
        return head;

    head->next = deleteDuplicates(head->next);

    if (head->val == head->next->val) {
        return head->next;
    } else {
        return head;
    }

    return head;
}


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

题目描述

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

示例 1:




输入:head = [1,2,3,3,4,4,5]

输出:[1,2,5]

示例 2:



输入:head = [1,1,1,2,3]

输出:[2,3]

提示:

  • 链表中节点数目在范围 [0, 300] 内
  • -100 <= Node.val <= 100
  • 题目数据保证链表已经按升序 排列

解题方案

  • C
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL) {
        return head;
    }
    // 定义一个新节点用来指向头节点,以防头节点被删除
    struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode));
    pre->next = head;            // 将新节点指向头节点
    struct ListNode* temp = pre; // 定义一个临时链表指针指向新节点

    while (temp->next && temp->next->next) {
        if (temp->next->val == temp->next->next->val) {
            int value = temp->next->val; // 保存这个值
            while (temp->next && temp->next->val == value) {
                temp->next = temp->next->next; // 删除相同节点
            }
        } else {
            temp = temp->next;
        }
    }
    return pre->next;
}

复杂度分析:

时间复杂度为 O(n),其中 n 是链表的长度。

空间复杂度为 O(1)。

相关文章
|
9月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
97 1
|
3月前
|
机器学习/深度学习 存储 算法
【LeetCode 热题100】347:前 K 个高频元素(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 347——前 K 个高频元素的三种解法:哈希表+小顶堆、哈希表+快速排序和哈希表+桶排序。每种方法都附有清晰的思路讲解和 Go 语言代码实现。小顶堆方法时间复杂度为 O(n log k),适合处理大规模数据;快速排序方法时间复杂度为 O(n log n),适用于数据量较小的场景;桶排序方法在特定条件下能达到线性时间复杂度 O(n)。文章通过对比分析,帮助读者根据实际需求选择最优解法,并提供了完整的代码示例,是一篇非常实用的算法学习资料。
249 90
|
1月前
|
存储
203. 移除链表元素,707.设计链表,206. 反转链表
链表是数据结构中的重要概念,包含单链表、双链表和循环链表。单链表每个节点存储数据与下一节点指针;双链表增加上一节点指针;循环链表首尾相连。 **例题解析:** 1. **203. 移除链表元素**:通过遍历链表删除指定值节点,注意处理头节点特殊情况。 2. **707. 设计链表**:实现链表的增删查操作,需理解指针操作逻辑,避免直接修改目标节点。 3. **206. 反转链表**:采用双指针或递归方法改变节点指向,完成链表反转。 以上题目涵盖链表核心操作,掌握后可灵活应对相关问题。
|
3月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
116 10
|
9月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
88 0
|
9月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
108 0
|
9月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
86 0
|
9月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
199 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表

热门文章

最新文章