力扣82删除排序链表中的重复元素 II：思路分析+代码实现+方法总结（三指针法&快慢指针法【双指针】&递归法）

淡淡的烟草味﹌ 2024-04-24 14:39 2阅读 0赞

#### 文章目录 ####

*  第一部分：题目描述
 *  第二部分：代码实现
 *   *  2.1 三指针法
     *  2.2 快慢指针法（双指针）
     *  2.3 递归

## 第一部分：题目描述 ##

🏠 链接：[82. 删除排序链表中的重复元素 II - 力扣（LeetCode）][82. _ II - _LeetCode]

⭐ 难度：中等

![image-20230515032300743][]

## 第二部分：代码实现 ##

### 2.1 三指针法 ###

p1 是待删除的上一个节点，每次循环对比 p2、p3 的值。

*  如果 p2 与 p3 的值重复，那么 p3 继续后移，直到找到与 p2 不重复的节点，p1 指向 p3 完成删除。
 *  如果 p2 与 p3 的值不重复，p1，p2，p3 向后平移一位，继续上面的操作。
 *  p2 或 p3 为 null 退出循环。
    
     *  p2 为 null 的情况，比如链表为 1 1 1 null。

p1 p2 p3
    s, 1, 1, 1, 2, 3, null
    
    p1 p2    p3
    s, 1, 1, 1, 2, 3, null
    
    p1 p2       p3
    s, 1, 1, 1, 2, 3, null
    
    p1 p3
    s, 2, 3, null
    
    p1 p2 p3
    s, 2, 3, null
    
       p1 p2 p3
    s, 2, 3, null

代码：

class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            // 当链表无节点或者只存在头节点，直接返回 null / 头节点
            if (head == null || head.next == null) {
        
                return head;
            }
    
            // 设置一个哨兵节点（伪头节点）
            ListNode sentinel = new ListNode(-999, head);
            // p1 指向哨兵节点
            ListNode p1 = sentinel;
            ListNode p2, p3;
    
            // 设置 p2 为 p1 的下一个节点，p3 为 p1 的下下个节点
            // 如果 此时 p2 或 p3 为空节点说明已遍历完链表，再无重复节点
            while ((p2 = p1.next) != null
                    && (p3 = p2.next) != null) {
        
    
                // 如果 p2 与 它的下一个节点val值重复，则需要删除当前p2、p3指向的节点以及后面与p2.val相同值的节点
                if (p2.val == p3.val) {
        
    
                    // 使用 p3 继续向后遍历，直到找到与p2.val不相同值的节点
                    while ((p3 = p3.next) != null && p3.val == p2.val) {
        
                    }
    
                    // 此时 p3 指向的节点为不想同值的节点
    
                    // 为了跳过当前 p2 到 p3以前 的节点，可以将p2的上一个节点p1的next 指向p3
                    p1.next = p3;
    
                    // 继续下一次循环即可，在循环条件中再次对p2、p3赋值使得p2、p3分别指向p1的下个节点与下下个节点
                } else {
        
                    // 如果 p2 与 它的下一个节点p3的val值不重复，说明链表中不存在与 p2.val 相等的值的节点，
                    // 则只需要将 p1、p2、p3后挪一位即可，由于在外层while循环中会对p2、p3赋值，因此在这里只需要对p1后移即可
                    p1 = p1.next;
                }
            }
    
            // 返回真正的头节点
            return sentinel.next;
        }
    }

### 2.2 快慢指针法（双指针） ###

class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            // 如果链表无节点或者只有一个节点，则返回 null / head
            if (head == null || head.next == null) {
        
                return head;
            }
    
            // 设置一个哨兵 sentinel，它的下一个节点为链表头节点 head
            ListNode sentinel = new ListNode(-999, head);
            // 快指针，指向 head
            ListNode fast = head;
            // 慢指针，指向 哨兵
            ListNode slow = sentinel;
            // 记录某个值出现次数
            int count = 0;
    
            // 使用快指针进行遍历链表
            while (fast != null) {
        
                // 如果快指针指向的val与慢指针下一个节点的val相等
                if (fast.val == slow.next.val) {
        
                    // 则fast继续向后遍历
                    fast = fast.next;
                    // 值出现次数 +1
                    count++;
                } else {
        
                    // 如果fast遇到与慢指针下一个节点的val不重复的值
    
                    // 判断 慢指针下一个节点的val出现次数即 count 是否为1
                    if (count == 1) {
        
                        // 如果只出现了一次，说明未出现重复的值，则慢指针向后移动一位即可
                        // 此时fast的位置一定是在 slow 的后面一位
                        slow = slow.next;
                    } else {
        
                        // 如果出现了多次，则需要忽略所有与 slow.next.val 具有相等值的节点
                        // 如何忽略呢？只需要更新slow的下一个节点为fast即可
                        slow.next = fast;
                    }
    
                    // 遇到了不重复的值，做完了对上一个count的处理后，重新清0进行下一次计算
                    count = 0;
                }
            }
    
            // 当 fast 为空时会退出循环，但并未对count进行后续处理，因此这里还需要处理一下
            // 如果不为1，说明出现了重复节点，如何忽略这些重复节点呢？只需要更新slow的下一个节点为null即可
            if (count != 1) {
        
                slow.next = null;
            }
    
            // 返回真正的头节点
            return sentinel.next;
        }
    }

### 2.3 递归 ###

递归函数负责返回：从当前节点（我）开始，完成去重的链表。

1.  若我与 next 重复，一直找到下一个不重复的节点，以它的返回结果为准。
2.  若我与 next 不重复，返回我，同时更新 next。

// 链表：1 -> 1 -> 1 -> 2 -> 3
    
    deleteDuplicates(ListNode p = 1) {
        
        // 找下个不重复的
    	deleteDuplicates(ListNode p = 1) {
        
            deleteDuplicates(ListNode p = 1) {
        
    			deleteDuplicates(ListNode p = 2) {
        
                    2.next=deleteDuplicates(ListNode p = 3) {
        
    					// 只剩一个节点，返回
                        return 3
                    }
                    return 2
    			}
            }
        }
    }

代码：

class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            // 边界节点的考虑
            if (head == null || head.next == null) {
        
                return head;
            }
    
            // 如果节点的val重复，则删除所有为val的节点
            if (head.val == head.next.val) {
        
                // 找到下下个节点
                ListNode tmp = head.next.next;
                // 循环遍历后面节点直到找到一个与当前节点val不同的节点
                while (tmp != null && tmp.val == head.val) {
        
                    tmp = tmp.next;
                }
    
                // 找到的tmp就是与 head 取值不相同的节点
                // 直接舍弃从head开始的这一部分节点，
                // 从 tmp 开始继续递归调用，return返回的节点一般是作为某个节点的下一个节点以达到舍弃的效果
                return deleteDuplicates(tmp);
            }
    
            // 如果不重复，就更新它的next节点，实际是对后续的节点进行去重操作
            head.next = deleteDuplicates(head.next);
            // 更新next后，返回当前这个不重复的节点即可
            return head;
        }
    }

[82. _ II - _LeetCode]: https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/submissions/
[image-20230515032300743]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/f4dd7d9cbe2945f3be692d2190c52c2b.png