题目描述#

给你一个已经按升序排好的链表 head，要求把所有出现过重复的数字对应节点全部删除，只保留那些只出现一次的节点。

最后返回的链表仍然需要保持有序，所以关键在于识别“某个值是否重复出现”，并把这一整段重复值全部跳过去，而不是只删除其中一个节点。

思路#

这份代码先创建了一个哑节点 dummy，让它指向原链表头部，再用 cur 指向 dummy。这样做的好处是，即使链表开头就是一整段重复元素，也可以统一通过修改 cur.Next 来删除，不需要单独处理头节点被删掉的情况。

因为链表本身已经有序，所以如果 cur.Next.Val == cur.Next.Next.Val，就说明当前值重复了。代码里把这个重复值记录到 x 里，然后不断执行 cur.Next = cur.Next.Next，把后面所有值等于 x 的节点整段跳过去。这样留下来的就只会是下一个不同的值。

如果当前两个相邻节点的值不同，说明 cur.Next 这个节点目前可以保留，于是让 cur 向后移动一位，继续检查后面的部分。整个过程始终围绕“当前节点的下一个节点是否应该保留”来展开，所以链表连接关系会比较清晰。

由于每个节点最多被访问和删除一次，时间复杂度是 O(n)，额外只用了常数个指针和变量，空间复杂度是 O(1)。

代码#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy
	x := -10001
	for cur.Next != nil && cur.Next.Next != nil {
		if cur.Next.Val == cur.Next.Next.Val {
			x = cur.Next.Val
			for cur.Next != nil && cur.Next.Val == x {
				cur.Next = cur.Next.Next // 跳过下一个节点
			}
		} else {
			cur = cur.Next
		}
	}
	return dummy.Next
}