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

叁歲伎倆 2023-02-16 12:13 20阅读 0赞

#### 题目描述 ####

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

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

示例 2:

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

#### 解题思路 ####

之前做了一道和这个差不多的题：[【LeetCode 83】删除排序链表中的重复元素][LeetCode 83]，比这个题目相对简单一点，直接使用CURD操作就搞定，但是这个题目需要考虑更多的内容。

我们在删除节点时，需要把节点的前驱结点和后驱节点都删除掉。我们想要获取一个节点的前驱节点，就需要设置一个虚拟的头结点来实现，虚拟的头结点指向真正的头结点，这样就确保每个节点都有前驱结点。

需要注意的是，重复的节点可能不只有两个，所以，我们还需要往后验证，反复进行判断和删除操作，直到没有重复的元素为止。

#### 代码实现 ####

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {ListNode} */
    var deleteDuplicates = function(head) { 
        // 处理链表只有0或1个节点的情况
        if(!head||!head.next){ 
            return head
        }
        // 设置虚拟头节点
        let dummy = new ListNode()
        dummy.next = head
        // 设置当前节点
        let cur = dummy
    
        while (cur.next &&cur.next.next){ 
            if(cur.next.val === cur.next.next.val){ 
                // 保存重复节点的值
                let val =cur.next.val
                // 反复判断是否还有相等的节点
                while(cur.next &&cur.next.val === val)
                { 
                    cur.next = cur.next.next
                }
            }else{ 
                cur = cur.next
            }
        }
        // 返回最终结果，也就是链表的起始的节点
        return dummy.next
    };

#### 提交结果 ####

![在这里插入图片描述][20200609213457130.png]

[LeetCode 83]: https://blog.csdn.net/qq_42033567/article/details/106650954
[20200609213457130.png]: https://img-blog.csdnimg.cn/20200609213457130.png