📃 题目描述

题目链接：83. 删除排序链表中的重复元素 (opens new window)

🔔 解题思路

方法一

使用两个指针，一个指针指向某段重复元素的第一个节点，另一个指针用来扫描重复元素。当遇到重复出现的节点时，直接遍历到该重复节点的末尾，然后删除两个指针中间这一段重复节点。

本题不需要头节点，因为根据题意，第一个节点是不可能被删除的

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 不需要头节点，因为根据题意，第一个节点是不可能被删除的

        // 指向重复元素的第一个节点
        ListNode left = head;
        // 扫描重复元素
        ListNode right = left.next;

        while (right != null) {
            // 遇到重复出现的节点
            if (left.val == right.val) {
                // 循环遍历到该重复节点的末尾的下一个元素
                while (right != null && left.val == right.val) {
                    right = right.next;
                }

                // 删除中间这一段重复节点
                left.next = right;
            }

            // 更新 left 和 right
            left = right;
            if (left != null) {
                right = left.next;
            }
        }

        return head;
    }
}

方法二（推荐）

一个指针就能解决，推荐这种写法：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;

        while (cur != null) {
            while (cur.next != null && cur.next.val == cur.val) {
                cur.next = cur.next.next;
            }

            cur = cur.next;
        }

        return head;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：