问题分析

我们有一个已经按升序排列的链表。我们的目标是删除所有重复的元素，确保每个元素只出现一次。

关键洞察： 因为链表是有序的，所以所有重复的元素都会相邻地排列在一起。这让问题变得简单，我们只需要检查当前节点和它后面的一个节点即可。

方法一：迭代法（最优解）

这是解决这个问题的最直观、最高效的方法。我们只需要一次遍历就可以完成所有删除操作。

思路：

1. 首先处理边界情况：如果链表为空或只有一个节点，那么它本身就没有重复元素，可以直接返回 head。
2. 初始化一个指针 current，让它指向链表的头节点 head。这个指针将用来遍历整个链表。
3. 当 current 的下一个节点（current.next）不为空时，持续循环：
   • 比较 current.val 和 current.next.val。
   • 如果它们的值相等，说明找到了重复元素。我们需要“跳过”current.next 这个节点。这可以通过将 current.next 指向 current.next.next 来实现。
   • 如果它们的值不相等，说明 current 指向的这个节点是唯一的，我们不需要删除它。将 current 指针向后移动一位，即 current = current.next。
4. 循环结束后，head 指向的链表就是已经删除了重复元素的新链表。返回 head。

代码实现：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 1. 处理边界情况
        if not head or not head.next:
            return head
            
        # 2. 初始化指针
        current = head
        
        # 3. 遍历链表
        while current.next:
            # 4. 比较当前节点和下一个节点的值
            if current.val == current.next.val:
                # 如果相等，跳过下一个节点
                current.next = current.next.next
            else:
                # 如果不相等，移动 current 指针
                current = current.next
                
        # 5. 返回修改后的链表头
        return head

复杂度分析：

• 时间复杂度: O(n)。其中 n 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度: O(1)。我们只使用了一个额外的指针变量 current，没有使用任何与链表长度成正比的额外空间。

评价： 这个迭代方法已经是该问题的最优解。它的时间和空间复杂度都是最佳的，并且逻辑清晰，易于理解和实现。

方法二：递归法（更优雅的实现）

递归的思路也非常简洁。我们可以将问题分解为：处理头节点，然后递归处理剩余的链表。

思路：

1. 基线条件（Base Case）：如果链表为空或只有一个节点，直接返回 head。
2. 递归步骤：
   • 对 head.next 进行递归调用，并将返回的结果赋值给 head.next。这一步的含义是：“先把我后面的链表处理干净，然后再接到我身上”。
   • 递归调用返回后，head.next 指向的就是一个已经没有重复元素的链表了。
   • 最后，我们只需要比较 head.val 和 head.next.val。
   • 如果它们相等，说明 head 和它后面的节点重复了，我们应该返回 head.next（相当于删除了 head）。
   • 如果它们不相等，说明 head 是唯一的，我们应该返回 head。

代码实现：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 1. 基线条件
        if not head or not head.next:
            return head
            
        # 2. 递归处理剩余部分，并将结果链接回来
        head.next = self.deleteDuplicates(head.next)
        
        # 3. 比较当前节点和处理后的下一个节点
        if head.val == head.next.val:
            # 如果相等，删除当前节点（返回下一个节点）
            return head.next
        else:
            # 如果不相等，保留当前节点
            return head

复杂度分析：

• 时间复杂度: O(n)。每个节点都需要被访问一次。
• 空间复杂度: O(n)。在最坏的情况下（链表中没有重复元素），递归调用的深度会达到 n，因此需要 O(n) 的调用栈空间。

评价： 递归解法的代码非常简洁、优雅，是对递归思想的完美应用。但由于其 O(n) 的空间复杂度，在性能上不如迭代法，并且在链表很长时可能导致栈溢出。

总结与对比

结论：

• 迭代法 是最高效和最推荐的解法，尤其是在处理大型数据结构时。
• 递归法 是一种非常好的思维锻炼，能展示你对递归的深刻理解。在面试中，能够提供两种解法并分析它们的优劣，会是一个非常加分的表现。