第一部分：题目描述
🏠 链接：83. 删除排序链表中的重复元素 - 力扣（LeetCode）
⭐ 难度：简单
第二部分：代码实现
2.1 快慢指针法
步骤：
- 当节点数小于2时，则不会发生重复节点的情况，无需删除，直接返回。
- 设置快慢指针，慢指针指向头节点head，快指针指向 head 的下一个节点。
- 使用fast指针遍历链表，每次对 fast.val 与 slow.val 进行比较。
- 快慢指针的val值相等，说明当前链表中还存与当前slow指向节点的值相等的节点。不需要理会当前fast指向的节点，直接向后移动一位。当 fast和last的val值不相等的时候，将slow的下一个节点设置为fast即可达到跳过重复节点的效果。
- 快慢指针的val值不相等，说明不再存在与当前slow指向的值相等的其他节点。设置 slow 的下一个节点为当前 fast 指向的节点来达到跳过重复节点的效果，slow后移，fast后移。
- fast 已遍历完链表，为null，slow 也应该指向 null，以跳过 slow 与 fast 之间的节点（肯定是重复节点）。
- 返回头节点。
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 递归
递归函数负责返回：从当前节点（我）开始，完成去重的链表
- 若我与 next 重复，返回 next
- 若我与 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; } } }
