Easy

题目描述

给定一个已排序的链表的头 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. 首先处理边界情况：如果链表为空，直接返回null
  2. 使用一个指针current从头节点开始遍历
  3. 当current和current.next都不为空时：
    • 如果current.val == current.next.val，说明有重复，删除current.next节点
    • 否则，移动current到下一个节点
  4. 重复步骤3直到遍历完成

这种方法的优点是只需要一次遍历，时间复杂度为O(n)，空间复杂度为O(1)，是最优解法。

代码实现

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) return head;
        
        ListNode* current = head;
        while (current->next) {
            if (current->val == current->next->val) {
                ListNode* nodeToDelete = current->next;
                current->next = current->next->next;
                delete nodeToDelete;
            } else {
                current = current->next;
            }
        }
        
        return head;
    }
};

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        current = head
        while current.next:
            if current.val == current.next.val:
                current.next = current.next.next
            else:
                current = current.next
        
        return head

public class Solution {
    public ListNode DeleteDuplicates(ListNode head) {
        if (head == null) return head;
        
        ListNode current = head;
        while (current.next != null) {
            if (current.val == current.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        
        return head;
    }
}

var deleteDuplicates = function(head) {
    if (!head) return head;
    
    let current = head;
    while (current.next) {
        if (current.val === current.next.val) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历整个链表一次，其中n为链表长度
空间复杂度O(1)只使用了常数个额外变量，没有使用额外的数据结构

相关题目