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、思路

由于链表已排序，因此可以通过迭代的方式删除重复元素。用一个指针遍历链表，当发现当前节点的值与下一个节点的值相同时，就删除下一个节点。

2、代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    // 初始化当前指针为链表头部
    current := head

    // 遍历链表，直到当前指针为nil或当前指针的下一个指针为nil
    for current != nil && current.Next != nil {
        // 检查当前节点的值是否与下一个节点的值相同
        if current.Val == current.Next.Val {
            // 如果相同，删除下一个节点（即跳过下一个节点）
            current.Next = current.Next.Next
        } else {
            // 如果不同，移动当前指针到下一个节点
            current = current.Next
        }
    }
    // 返回处理后的链表头部
    return head
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。
• 空间复杂度：O(1)，只需要常数级别的额外空间。

三、总结

方案	时间复杂度	空间复杂度	备注
迭代法	O(n)	O(1)	直接在链表上进行操作

迭代法是解决这个问题的有效方法，因为它直接在链表上进行操作，不需要额外的空间。在实际应用中，这是解决此类问题的首选方法。