学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

图一

图二

示例 1：（图一）
输入：head = [1,1,2]
输出：[1,2]示例 2：（图二）
输入：head = [1,1,2,3,3]
输出：[1,2,3]

我的思路
两个思路，一个是循环，一个是递归
网上思路
双指针

我的思路

解法一：循环

var deleteDuplicates = function(head) {let current = head;while (current && current.next) {if (current.val === current.next.val) {current.next = current.next.next; } else {current = current.next;}}return head;
};

讲解

1. 初始化指针：创建一个指针 current 指向链表的头节点。
2. 遍历链表：遍历链表直到 current.next 为空。
3. 检查重复：如果当前节点 current 的值与下一个节点 current.next 的值相同，则跳过下一个节点，即将 current.next 设置为 current.next.next。
4. 继续遍历：如果当前节点 current 的值与下一个节点 current.next 的值不同，则将 current 指针移动到下一个节点。
5. 返回结果：遍历完成后返回链表的头节点。

解法二：递归

var deleteDuplicates = function (head) {if (head === null || head.next === null) return head;if (head.next.val === head.val) {head.next = head.next.next;return deleteDuplicates(head);} else {head.next = deleteDuplicates(head.next);return head;}
};

讲解

1. 如果链表为空（head === null） 或只有一个节点 （head.next === null），则返回头节点，因为没有重复节点需要删除。
2. 如果当前节点的值与下一个节点的值相同**（head.next.val === head.val）**，则说明存在重复节点。
3. 通过 head.next = head.next.next，我们将当前节点的 next 指向下一个节点的下一个节点，从而跳过了重复节点。
4. 然后递归调用 deleteDuplicates(head)，继续检查当前节点**（head）**的下一个节点。
5. 如果当前节点的值与下一个节点的值不相同，说明没有重复节点。
6. 递归调用 deleteDuplicates(head.next) 处理下一个节点，并将返回的结果赋值给 head.next，以确保链表的结构保持正确。

网上思路

var deleteDuplicates = function (head) {if (!head) return head;let prev = head;let current = head.next;while (current) {if (current.val === prev.val) {prev.next = current.next;} else {prev = current;}current = current.next;}return head;
};

讲解

1. 初始化指针：
   prev 指向链表的头节点。
   current 指向头节点的下一个节点。
2. 遍历链表：
   使用 while (current) 来遍历整个链表
3. 检查重复：
   如果 current.val 和 prev.val 相同，说明存在重复。
   prev.next = current.next：通过调整 prev 的 next 指针，跳过重复的节点。
4. 移动指针：
   如果当前节点和前一个节点的值不同，则移动 prev 指针到当前节点。
   无论是否有重复，current 指针始终向前移动。

删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

图三

图四

示例 1：（图三）
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]示例 2：（图四）
输入：head = [1,1,1,2,3]
输出：[2,3]

我的思路
双指针
网上思路
递归

我的思路

var deleteDuplicates = function (head) {let dummy = new ListNode(0, head);let prev = dummy;let curr = head;while (curr && curr.next) {if (curr.val === curr.next.val) {while (curr.next && curr.val === curr.next.val) {curr = curr.next;}prev.next = curr.next;} else {prev = prev.next;}curr = curr.next;}return dummy.next;
};

讲解

1. 创建哑节点：为了方便处理头节点可能被删除的情况，我们可以在链表前面添加一个哑节点。
2. 初始化指针：创建一个指针 prev 指向哑节点，创建一个指针 curr 指向链表的头节点。
3. 遍历链表：遍历链表直到 curr 到达末尾。
4. 检查重复：如果当前节点 curr 的值与下一个节点 curr.next 的值相同，则继续向前遍历直到找到一个不同的节点。
5. 连接不同节点：一旦找到不同的节点，将 prev.next 设置为这个不同的节点。
6. 更新指针：如果没有重复节点，则将 prev 和 curr 都移动到下一个节点。
7. 返回结果：遍历完成后返回哑节点的下一个节点作为新的头节点。

网上思路

var deleteDuplicates = function (head) {if (!head || !head.next) return headif (head.val === head.next.val) {while (head.next && head.next.val === head.val) head.next = head.next.nextreturn deleteDuplicates(head.next)} else {head.next = deleteDuplicates(head.next)}return head
};

讲解

1. 基本情况检查:
   if (!head || !head.next) return head：如果链表为空**（head 为 null）或者只有一个节点（head.next 为 null）**，则直接返回 head。这是递归的基本情况，表示链表已经处理完成。
2. 检查当前节点与下一个节点的值:
   if (head.val === head.next.val)：检查当前节点的值是否与下一个节点的值相同。如果相同，说明存在重复节点。
3. 跳过重复节点:
   while (head.next && head.next.val === head.val) head.next = head.next.next：使用 while 循环，继续跳过所有与当前节点值相同的节点， 直到找到一个不同的节点或到达链表末尾。
4. 递归调用:
   return deleteDuplicates(head.next)：在跳过所有重复节点后，递归调用 deleteDuplicates 处理下一个节点，并返回处理后的链表。
5. 处理不同的节点:
   else { head.next = deleteDuplicates(head.next) }：如果当前节点的值与下一个节点的值不同，递归调用 deleteDuplicates 处理下一个节点，并将返回的结果赋值给 head.next。
6. 返回处理后的头节点:
   return head：最后，返回处理后的链表头节点。

总结

链表的题目写了这么多天，好像都可以用递归来解题，今天尝试了一下，还是不错的，后面可以再多尝试尝试。