删除排序链表中的重复元素 II（LeetCode）

题目

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

解题

class ListNode:     def __init__(self, val=0, next=None):         self.val = val         self.next = next   class Solution:     def deleteDuplicates(self, head: ListNode) -> ListNode:         # 创建一个虚拟头结点         dummy = ListNode(0)         dummy.next = head         prev = dummy          while head:             # 检查当前节点是否是重复节点             if head.next and head.val == head.next.val:                 # 找到所有重复的节点                 while head.next and head.val == head.next.val:                     head = head.next                 # 跳过所有重复的节点                 prev.next = head.next             else:                 # 如果没有重复，更新 prev                 prev = prev.next              # 移动到下一个节点             head = head.next          return dummy.next   # 工具函数 def print_linked_list(head: ListNode):     """打印链表中的所有节点值"""     current = head     while current:         print(current.val, end=" -> " if current.next else "\n")         current = current.next   def list_to_linked_list(values):     """将列表转换为链表"""     if not values:         return None     dummy = ListNode(0)     current = dummy     for value in values:         current.next = ListNode(value)         current = current.next     return dummy.next   def linked_list_to_list(head: ListNode):     """将链表转换为列表"""     result = []     current = head     while current:         result.append(current.val)         current = current.next     return result   # 测试代码 if __name__ == "__main__":     # 测试案例     test_cases = [         ([1, 1, 1, 2, 3], [2, 3]),  # 删除重复元素后的链表         ([1, 1, 2, 3, 3], [2]),  # 删除重复元素后的链表         ([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),  # 无重复元素         ([1, 1, 2, 2, 3, 3], []),  # 所有元素都重复         ([1, 2, 3, 4, 4, 5, 5], [1, 2, 3])  # 删除重复元素后的链表     ]      for i, (values, expected) in enumerate(test_cases):         head = list_to_linked_list(values)         solution = Solution()         print(f"测试用例 {i + 1}: 原链表：", end="")         print_linked_list(head)         new_head = solution.deleteDuplicates(head)         result = linked_list_to_list(new_head)         print(f"删除重复元素后的链表：", end="")         print_linked_list(new_head)         assert result == expected, f"测试失败：期望 {expected}, 但得到 {result}"         print("测试通过\n") 

测试用例 1: 原链表：1 -> 1 -> 1 -> 2 -> 3
删除重复元素后的链表：2 -> 3
测试通过

测试用例 2: 原链表：1 -> 1 -> 2 -> 3 -> 3
删除重复元素后的链表：2
测试通过

测试用例 3: 原链表：1 -> 2 -> 3 -> 4 -> 5
删除重复元素后的链表：1 -> 2 -> 3 -> 4 -> 5
测试通过

测试用例 4: 原链表：1 -> 1 -> 2 -> 2 -> 3 -> 3
删除重复元素后的链表：测试通过

测试用例 5: 原链表：1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 5
删除重复元素后的链表：1 -> 2 -> 3
测试通过