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

ゝ一世哀愁。 2024-04-24 14:39 2阅读 0赞

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

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

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

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

⭐ 难度：简单

![image-20230514010912170][]

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

### 2.1 快慢指针法 ###

步骤：

1.  当节点数小于2时，则不会发生重复节点的情况，无需删除，直接返回。
2.  设置快慢指针，慢指针指向头节点head，快指针指向 head 的下一个节点。
3.  使用fast指针遍历链表，每次对 fast.val 与 slow.val 进行比较。
    
     *  快慢指针的val值相等，说明当前链表中还存与当前slow指向节点的值相等的节点。不需要理会当前fast指向的节点，直接向后移动一位。当 fast和last的val值不相等的时候，将slow的下一个节点设置为fast即可达到跳过重复节点的效果。
     *  快慢指针的val值不相等，说明不再存在与当前slow指向的值相等的其他节点。设置 slow 的下一个节点为当前 fast 指向的节点来达到跳过重复节点的效果，slow后移，fast后移。
4.  fast 已遍历完链表，为null，slow 也应该指向 null，以跳过 slow 与 fast 之间的节点（肯定是重复节点）。
5.  返回头节点。

class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            // 当节点数小于2时，则不会发生重复节点的情况，无需删除，直接返回
            if (head == null || head.next == null) {
        
                return head;
            }
            // 慢指针
            ListNode slow = head;
            // 快指针，初始指向 head 的下一个节点
            ListNode fast = head.next;
    
            // fast 遍历链表，fast == null 说明遍历完成
            while (fast != null) {
        
                if (slow.val == fast.val) {
        
                    // 情况一：快慢指针的val值相等，说明当前链表中还存与当前slow指向节点的值相等的节点
    
                    // 不需要理会当前fast指向的节点，直接向后移动一位
                    // 当 fast和last的val值不相等的时候，将slow的下一个节点设置为fast即可达到跳过重复节点的效果
                    fast = fast.next;
                } else {
        
                    // 情况二：快慢指针的val值不相等，说明不再存在与当前slow指向的值相等的其他节点
    
                    // 2.1 设置 slow 的下一个节点为当前 fast 指向的节点
                    slow.next = fast;
                    // 2.2 slow 向后移动
                    slow = slow.next;
                    // 2.3 fast 向后移动
                    fast = fast.next;
                }
            }
    
            // fast 已遍历完链表，为null，slow 也应该指向空
            // 例如链表：1 -> 1 -> 3 -> 3 -> null
            // fast为null时，slow 为第一个3，则需要跳过第二个3，那么 slow 指向 null 或者 fast 即可 
            slow.next = null;
    
            // 返回头节点
            return head;
        }
    }

### 2.2 递归 ###

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

1.  若我与 next 重复，返回 next
2.  若我与 next 不重复，返回我，但 next 应当更新

deleteDuplicates(ListNode p=1) {
        
        deleteDuplicates(ListNode p=1) {
        
            1.next=deleteDuplicates(ListNode p=2) {
        
                2.next=deleteDuplicates(ListNode p=3) {
        
                    deleteDuplicates(ListNode p=3) {
        
    					// 只剩一个节点，返回
                        return 3
                    }                
                }
                return 2
            }
            return 1
        }
    }

代码：

class Solution {
        
        public ListNode deleteDuplicates(ListNode head) {
        
            // 如果无节点或到了最后一个节点，则返回 null 或 最后一个节点即可
            if (head == null || head.next == null) {
        
                return head;
            }
            if (head.val == head.next.val) {
        
                // 如果当前节点的val与下一个节点的val相等
                // 则返回下一个节点，就是不保留当前节点，只保留下一个节点
                return deleteDuplicates(head.next);
            } else {
        
                // 如果当前节点的val与下一个节点的val不相等
                // 则更新当前节点的next
                head.next = deleteDuplicates(head.next);
                // 返回当前节点
                return head;
            }
        }
    }

[83. _ - _LeetCode]: https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
[image-20230514010912170]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/1bd0e0d67eec4522aed7fdfe2f3afc66.png