18_链表_82. 删除排序链表中的重复元素 II.md

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

[TOC]

思路

条件反射想到快慢指针，仔细一思考，快慢指针还需要两个指针同时前进，似乎可以融合成一个指针。结合题目：重复元素可能出现在头部，故需要一个虚拟节点dummy。

解题方法

用 curr 记录当前节点，curr.next 记录慢指针，curr.next.next 记录快指针； 当快慢指针值相同时，记录下当前重复值，并将快慢指针后移，删除当前节点；比较后移后的慢指针值和重复值是否相同，相同则重复上述步骤，直至结束。

复杂度

• 时间复杂度:

添加时间复杂度: $O(n)$

Code

// 快慢指针：本题实际上需要用到三个指针：
// 虚拟节点：curr; 慢指针：curr.next; 快指针：curr.next.next
// 比较快慢指针的值是否相同，相同的话让快慢指针都向前移动，并且记录下重复的值
// 当快慢指针的值不同，且与重复值不同时，将虚拟节点的next指向慢指针
function deleteDuplicates(head: ListNode | null): ListNode | null {
    if (!head) return head

    // 创建一个虚拟节点
    let dummy = new ListNode(0, head)
    let curr = dummy
    // 比较快慢指针是否相同，相同的话将当前节点的下一个节点指向快指针所在位置
    while (curr.next && curr.next.next) {
        if (curr.next.val === curr.next.next.val) { // 快慢指针值相同
            const val = curr.next.val // 记录重复值
            while (curr.next && curr.next.val === val) { // 当慢指针与重复值相同时，指针向前移动
                curr.next = curr.next.next
            }
        } else { // 快慢指针不相同，将虚拟节点的next指向慢指针
            curr = curr.next
        }
    }

    return dummy.next
};