LeetCode 82. 删除排序链表中的重复元素 II

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 82. 删除排序链表中的重复元素 II

思路分析

双指针问题

参考代码

func deleteDuplicates(head *ListNode) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy

	for cur.Next != nil && cur.Next.Next != nil {
		if cur.Next.Val == cur.Next.Next.Val {
			// 跳过所有重复的节点
			val := cur.Next.Val
			for cur.Next != nil && cur.Next.Val == val {
				cur.Next = cur.Next.Next
			}
		} else {
			cur = cur.Next
		}
	}
	return dummy.Next
}

func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	dummy := &ListNode{Next： head}
	pre := dummy
	cur := head

	for cur != nil {
		if cur.Next != nil && cur.Val == cur.Next.Val {
			for cur.Next != nil && cur.Val == cur.Next.Val {
				cur = cur.Next
			}
			pre.Next = cur.Next
		} else {
			pre = pre.Next
		}
		cur = cur.Next
	}

	return dummy.Next
}

时间复杂度：O(n)，因为我们只遍历了一遍链表。

空间复杂度：O(1)，只使用了常数级别的额外空间。

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    if head.Val == head.Next.Val {
        // 跳过所有重复的节点
        for head.Next != nil && head.Val == head.Next.Val {
            head = head.Next
        }
        return deleteDuplicates(head.Next)
    } else {
        head.Next = deleteDuplicates(head.Next)
        return head
    }
}