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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii
• 标签: 一次遍历, 递归

解法一: 一次遍历

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    p := &ListNode{
        Val: -1000,
        Next: head,
    }
    cur := p
    for cur != nil {
        if cur.Next != nil && cur.Next.Next != nil && cur.Next.Val == cur.Next.Next.Val {
            curVal := cur.Next.Val
            for cur.Next != nil && curVal == cur.Next.Val {
                cur.Next = cur.Next.Next
            }
        } else {
            cur = cur.Next
        }
    }
    return p.Next
}

解法二: 递归

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    if head.Val == head.Next.Val {
        next := head.Next
        for next != nil && head.Val == next.Val {
            next = next.Next
        }
        return deleteDuplicates(next)
    }
    head.Next = deleteDuplicates(head.Next)
    return head
}