day139—链表—删除排序链表中的重复元素（LeetCode-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
• 题目数据保证链表已经按升序排列

解决方案：

这段代码的核心功能是删除升序单链表中的重复节点（仅保留每个元素的唯一实例，比如原链表 1→1→2→3→3 变为 1→2→3），采用「一次遍历 + 指针跳过重复节点」的方式实现，时间复杂度O(n)、空间复杂度O(1)，是该问题的经典最优解法。

核心逻辑

代码利用链表 “升序” 的特性，只需遍历一次即可识别并删除重复节点，无需额外空间：

1. 边界处理：若链表为空（head为nullptr），直接返回nullptr；
2. 遍历去重：用指针cur从链表头节点开始遍历，循环条件为cur->next不为空：
   • 若当前节点值等于下一个节点值（cur->val == cur->next->val），说明存在重复，将cur->next指向cur->next->next，跳过重复节点；
   • 若值不相等，说明无重复，将cur移动到下一个节点继续遍历；
3. 返回结果：遍历完成后，原链表已完成去重，返回头节点head即可。

总结

1. 核心思路：依托升序链表的特性，重复节点必相邻，通过 “跳过重复节点” 的指针操作完成去重；
2. 关键细节：仅当节点值不相等时才移动cur，避免漏删连续重复的节点；
3. 效率特点：一次遍历完成所有去重操作，时间O(n)、空间O(1)，是升序链表去重的最优解法。

函数源码：

/** * 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 nullptr; ListNode* cur=head; while(cur->next){ if(cur->val==cur->next->val){ cur->next=cur->next->next; } else{ cur=cur->next; } } return head; } };