56 删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中所有重复的结点，重复的结点不保留。

示例：

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

解题思路

核心思想：使用虚拟头节点，简化操作。

关键步骤：

1. 创建虚拟头节点，指向原头节点
2. 遍历链表，比较当前节点和下一个节点的值
3. 如果相同，跳过所有相同节点
4. 如果不同，正常链接

时间复杂度：O(n) 空间复杂度：O(1)

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def delete_duplication(head):
    """
    删除链表中重复的节点

    Args:
        head: 链表头节点

    Returns:
        ListNode: 删除后的头节点
    """
    if not head:
        return None

    # 虚拟头节点
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while head and head.next:
        if head.val == head.next.val:
            # 找到所有相同节点
            value = head.val
            while head and head.val == value:
                head = head.next
            prev.next = head
        else:
            prev = head
            head = head.next

    return dummy.next


# 测试代码
if __name__ == "__main__":
    # 创建链表: 1->2->3->3->4->4->5
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(3)
    head.next.next.next.next = ListNode(4)
    head.next.next.next.next.next = ListNode(4)
    head.next.next.next.next.next.next = ListNode(5)

    result = delete_duplication(head)

    # 打印结果
    while result:
        print(result.val, end="->")
        result = result.next
    print("None")

# 输出:
# 1->2->5->None