【力扣】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)。

相关文章
|
10天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
12 2
【数据结构OJ题】移除链表元素
|
18天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
18天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
18天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
21天前
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
10 1
|
15天前
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
链表4(法二)------7-4 sdut-C语言实验-单链表中重复元素的删除
12 0
|
17天前
2670.找出不同元素数目差数组-力扣(LeetCode)
2670.找出不同元素数目差数组-力扣(LeetCode)
8 0
|
18天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
21天前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
9 0
|
21天前
|
存储 算法 Java
力扣经典150题第四十五题:存在重复元素 II
力扣经典150题第四十五题:存在重复元素 II
11 0

热门文章

最新文章