一、题目描述

给定一个已排序的链表的头 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. 创建一个哑结点（dummy node），它的next指针指向链表的头节点。哑结点的目的是为了方便删除头节点。

3. 使用两个指针，current和next，分别指向哑结点和哑结点的下一个节点。

4. 遍历链表，比较current的下一个节点和下下个节点的值：

• 如果它们的值相同，则删除下下个节点。
• 如果它们的值不同，则将current指向下一个节点。

5. 继续遍历，直到current的下一个节点为空。

6. 返回哑结点的下一个节点，即新链表的头节点。

三、具体代码

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            if (current.next.val == current.next.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return dummy.next;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 我们遍历了整个链表一次，其中 n 是链表的长度。
• 在每次迭代中，我们进行了常数时间的操作，比如比较节点值和修改节点指向。
• 因此，总的时间复杂度是 O(n)。

2. 空间复杂度

• 我们只使用了固定数量的额外空间，即哑结点 dummy 和几个指针变量 current。
• 这些额外空间的使用不依赖于输入链表的大小，因此空间复杂度是 O(1)。

五、总结知识点

1. 链表（Linked List）：

• 链表是一种常见的基础数据结构，由一系列节点组成，每个节点包含数据和一个或多个指向其他节点的引用（链接）。
• 在这个问题中，我们操作的是单向链表，每个节点只包含数据和指向下一个节点的引用。

2. 哑结点（Dummy Node）：

• 哑结点是一个辅助节点，通常用于简化链表操作，尤其是在处理头节点时。
• 在这个问题中，哑结点被用来简化删除头节点的操作，因为头节点可能被重复删除。

3. 指针（Pointer）：

• 在链表的操作中，指针用于跟踪当前处理的节点。
• 在这个问题中，current 指针用于遍历链表，dummy 指针用于简化头节点的删除操作。

4. 循环（Loop）：

• 循环用于遍历链表中的每个节点。
• 在这个问题中，while 循环用于遍历链表，直到到达链表的末尾。

5. 链表操作：

• 链表的基本操作包括遍历、修改节点数据和修改节点指向。
• 在这个问题中，我们修改了节点的 next 指针，以删除重复的元素。

6. 条件语句（Conditional Statements）：

• 条件语句用于根据条件执行不同的代码路径。
• 在这个问题中，if 语句用于检查当前节点的下一个节点和下下个节点的值是否相等，以决定是否删除节点。

7. 算法设计：

• 这个问题涉及到简单的算法设计，即如何高效地删除链表中的重复元素。
• 通过利用链表的有序性，我们可以通过一次遍历来删除重复元素，这比先排序再删除重复元素更高效。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。