[M链表] lc82. 删除排序链表中的重复元素 II(单链表+好题+模拟)

发布时间:2024年01月15日

1. 题目来源

链接:82. 删除排序链表中的重复元素 II

相似题目:[E链表] lc83. 删除排序链表中的重复元素(单链表+模拟)

2. 题目解析

这个题目与 83 题都很类似,一个是将重复元素全部删除,另一个是将重复元素至多保留一个。注意以下几点即可:

  • 本题可能一个节点都不存在,且头结点也可能被删除发生改变。所以需要应用到虚拟头结点的这个技术。
  • 我们需要在链表中找到值相同的这一段链表,首位指针分别用 a,b 来标识,那么构成一个 [a, b) 区间,例如:1->2->3->3->3->4->NULL 链表,那么此时 a–>3(1),b指向4。显然,我们只需要让 a 的前一个指针的 next 指向 b 指针位置,即 a->next=b 即可。所以我们需要知道,3 的前一个位置,即 2 所在位置的指针。如果 2 的next的next 指针元素 b 与 2 的next 指针 a 一致,那么 b 指针向后移动,过滤掉重复元素,直到不相等的时候,现在有两种可能的情况:
    • 中间是没有重复元素的,不需要跳过重复元素
      • 没有重复元素,意味着 2 的 next 的 next 元素与 b 一致。此时就没有跳过任何元素,则 2 的这个指针向后一定一位即可。
    • 中间是有重复元素的,需要跳过重复元素
      • 反之,2 的这个指针需要指向 b 指针,跳过中间的重复元素。
  • 最终返回虚拟头结点的 next 指针即可
    在这里插入图片描述
    注意体会两点:
  • 找到重复元素段后,针对当前节点的 next 指针赋值,要区分情况。有重复段和无重复段,next 指针指向的位置是不一样的。
  • 比较两个链表元素节点是否一样,应该直接用 节点之间的 ==,而不是 val 的 == 哈

  • 时间复杂度 O ( n ) O(n) O(n)
  • 空间复杂度 O ( 1 ) O(1) O(1)

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head)
            return head;

        ListNode* dummy = new (ListNode){0, head};
        ListNode *a = dummy;
        while (a->next) {
            ListNode *b = a->next->next;
            while (b && (b->val == a->next->val)) b = b->next;
            if (a->next->next == b) a = a->next;
            else a->next = b;
        }

        return dummy->next;
    }
};
// @lc code=end

文章来源:https://blog.csdn.net/yl_puyu/article/details/135611191
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。