LeetCode 83题：删除排序链表中的重复元素【面试】

输入: 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
输出: 1 -> 2 -> 5

输入: 1 -> 1 -> 1 -> 2 -> 3
输出: 2 -> 3

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
def deleteDuplicates(head):
    """
    使用哨兵节点和双指针删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    sentinel = ListNode(0)  # 哨兵节点
    sentinel.next = head
    prev = sentinel  # 前指针
    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.next
        head = head.next
    return sentinel.next
# 示例调用
# 创建链表函数及打印函数假定已定义

def deleteDuplicates(head):
    """
    递归删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    if not head or not head.next:
        return head
    
    if head.val == head.next.val:
        while head.next and head.val == head.next.val:
            head = head.next
        return deleteDuplicates(head.next)
    else:
        head.next = deleteDuplicates(head.next)
        return head
# 示例调用代码
# 创建链表函数及打印函数假定已定义

def deleteDuplicates(head):
    """
    一次遍历删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    while current.next and current.next.next:
        if current.next.val == current.next.next.val:
            val = current.next.val
            while current.next and current.next.val == val:
                current.next = current.next.next
        else:
            current = current.next
    return dummy.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义

def deleteDuplicates(head):
    """
    使用哈希表记录频率，然后删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    from collections import Counter
    counter = Counter()
    node = head
    while node:
        counter[node.val] += 1
        node = node.next
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    while current.next:
        if counter[current.next.val] > 1:
            current.next = current.next.next
        else:
            current = current.next
    return dummy.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义

def deleteDuplicates(head):
    """
    使用快慢指针删除所有重复的元素
    :param head: ListNode, 链表的头节点
    :return: ListNode, 修改后的链表头节点
    """
    dummy = ListNode(0)
    dummy.next = head
    slow = dummy
    while head:
        if head.next and head.val == head.next.val:
            # 跳过当前的重复元素
            while head.next and head.val == head.next.val:
                head = head.next
            slow.next = head.next  # 连接到第一个不重复的元素
        else:
            slow = slow.next  # 不重复，慢指针前进
        head = head.next  # 快指针始终前进
    return dummy.next
# 示例调用代码
# 创建链表函数及打印函数假定已定义