83.删除排序链表中的重复元素
83.1 题目
给定一个已排序的链表的头 head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序排列
83.2 题解
迭代法
// 方法一：迭代法
// 不停的往后找节点，让当前节点指向后面不相等的节点，再重新移到当前节点，直到当前节点或者后一节点为空
static ListNode DeleteDuplicates1(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null)
return head;
// 创建一个指针变量 current，初始化为链表的头节点
ListNode current = head;
// 遍历链表，直到当前节点或者下一个节点为空
while (current != null && current.next != null)
{
// 如果当前节点的值和下一个节点的值相等
if (current.val == current.next.val)
{
// 删除下一个节点，将当前节点的 next 指向下下一个节点
current.next = current.next.next;
}
else
{
// 如果当前节点的值和下一个节点的值不相等，移动到下一个节点
current = current.next;
}
}
// 返回删除重复节点后的链表头节点
return head;
}
递归法
// 递归函数对链表的每个节点进行处理，将当前节点的 next 指针指向递归处理后的下一个节点。然后，通过比较当前节点和下一个节点的值，决定返回哪个节点.
static ListNode DeleteDuplicates2(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null)
return head;
// 递归调用 DeleteDuplicates2 方法，处理下一个节点
head.next = DeleteDuplicates2(head.next);
// 返回值的目的是返回下一节点
// 检查当前节点和下一个节点的值是否相等
// 如果相等，返回下一个节点，实现删除当前节点的效果
// 如果不相等，返回当前节点，保留当前节点
return head.val == head.next.val ? head.next : head;
}
双指针法
// 方法三：双指针法
// 使用两个指针（慢指针和快指针）来遍历链表，当慢指针和快指针所指节点的值相等时，删除快指针所指的节点，否则移动慢指针。
static ListNode DeleteDuplicates3(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null)
return head;
// 定义两个指针，一个指向当前节点，另一个指向当前节点的下一个节点
ListNode slow = head;
ListNode fast = head.next;
// 遍历链表
while (fast != null)
{
// 如果当前节点和下一个节点的值相等
if (slow.val == fast.val)
{
// 删除下一个节点，将当前节点的 next 指向下下一个节点
slow.next = fast.next;
}
else
{
// 如果当前节点和下一个节点的值不相等，移动到下一个节点
slow = slow.next;
}
// 将快指针移动到下一个节点
fast = fast.next;
}
// 返回删除重复节点后的链表头节点
return head;
}
直接遍历法
// 方法四：直接遍历法
// 遍历链表，使用两个指针 nowNode 和 findNode，其中 nowNode 表示当前节点，findNode 用于查找当前节点之后的与当前节点值相同的节点。
// 当 nowNode 与 findNode 值不相等时，将 nowNode 移动到下一个节点。
// 当 nowNode 与 findNode 值相等时，使用 findNode 进行迭代查找，直到 findNode 的值与 nowNode 的值不相等或者 findNode 到达链表末尾。
// 将 nowNode 的 next 指向 findNode，即跳过所有与当前节点值相同的节点。
// 返回处理后的链表头节点。
static ListNode DeleteDuplicates4(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null) return head;
// 初始化两个指针，nowNode 表示当前节点，findNode 用于查找与当前节点值相同的节点
ListNode nowNode = head;
ListNode findNode = head;
$$
// 遍历链表
while (nowNode.next != null)
{
// 如果当前节点和下一个节点的值不相等
if (nowNode.val != nowNode.next.val)
{
// 移动当前节点到下一个节点
nowNode = nowNode.next;
}
else
{
// 当前节点和下一个节点的值相等，使用 findNode 进行迭代查找
findNode = nowNode.next;
while (findNode.val == nowNode.val)
{
// 如果 findNode 的下一个节点不为空，继续向后查找
if (findNode.next != null)
{
findNode = findNode.next;
}
else
{
// 如果 findNode 到达链表末尾，则跳出循环
findNode = null;
break;
}
}
// 将当前节点的 next 指向 findNode，即跳过所有与当前节点值相同的节点
nowNode.next = findNode;
}
}
// 返回处理后的链表头节点
return head;
}
83.3 代码
using System;
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}
class Program
{
static void Main()
{
#region 题目
// 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次。
// 返回 已排序的链表。
// 示例 1：
// 输入：head = [1,1,2]
// 输出：[1,2]
// 示例 2：
// 输入：head = [1,1,2,3,3]
// 输出：[1,2,3]
// 提示：
// 链表中节点数目在范围 [0, 300] 内
// -100 <= Node.val <= 100
// 题目数据保证链表已经按升序排列
#endregion
#region 测试
// 示例 1
ListNode head1 = new ListNode(1, new ListNode(1, new ListNode(2)));
PrintList("示例1", "方法1", head1, DeleteDuplicates1(head1));
// 示例 2
ListNode head2 = new ListNode(1, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(3)))));
PrintList("示例2", "方法2", head2, DeleteDuplicates2(head2));
// 示例 3
ListNode head3 = new ListNode(1, new ListNode(1, new ListNode(1)));
PrintList("示例3", "方法3", head3, DeleteDuplicates3(head3));
// 示例 4
ListNode head4 = new ListNode(1, new ListNode(1, new ListNode(1)));
PrintList("示例4", "方法4", head4, DeleteDuplicates4(head4));
#endregion
}
#region 答案
// 方法一：迭代法
// 不停的往后找节点，让当前节点指向后面不相等的节点，再重新移到当前节点，直到当前节点或者后一节点为空
static ListNode DeleteDuplicates1(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null)
return head;
// 创建一个指针变量 current，初始化为链表的头节点
ListNode current = head;
// 遍历链表，直到当前节点或者下一个节点为空
while (current != null && current.next != null)
{
// 如果当前节点的值和下一个节点的值相等
if (current.val == current.next.val)
{
// 删除下一个节点，将当前节点的 next 指向下下一个节点
current.next = current.next.next;
}
else
{
// 如果当前节点的值和下一个节点的值不相等，移动到下一个节点
current = current.next;
}
}
// 返回删除重复节点后的链表头节点
return head;
}
// 方法二：递归法
// 递归函数对链表的每个节点进行处理，将当前节点的 next 指针指向递归处理后的下一个节点。然后，通过比较当前节点和下一个节点的值，决定返回哪个节点.
static ListNode DeleteDuplicates2(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null)
return head;
// 递归调用 DeleteDuplicates2 方法，处理下一个节点
head.next = DeleteDuplicates2(head.next);
// 返回值的目的是返回下一节点
// 检查当前节点和下一个节点的值是否相等
// 如果相等，返回下一个节点，实现删除当前节点的效果
// 如果不相等，返回当前节点，保留当前节点
return head.val == head.next.val ? head.next : head;
}
// 方法三：双指针法
// 使用两个指针（慢指针和快指针）来遍历链表，当慢指针和快指针所指节点的值相等时，删除快指针所指的节点，否则移动慢指针。
static ListNode DeleteDuplicates3(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null)
return head;
// 定义两个指针，一个指向当前节点，另一个指向当前节点的下一个节点
ListNode slow = head;
ListNode fast = head.next;
// 遍历链表
while (fast != null)
{
// 如果当前节点和下一个节点的值相等
if (slow.val == fast.val)
{
// 删除下一个节点，将当前节点的 next 指向下下一个节点
slow.next = fast.next;
}
else
{
// 如果当前节点和下一个节点的值不相等，移动到下一个节点
slow = slow.next;
}
// 将快指针移动到下一个节点
fast = fast.next;
}
// 返回删除重复节点后的链表头节点
return head;
}
// 方法四：直接遍历法
// 遍历链表，使用两个指针 nowNode 和 findNode，其中 nowNode 表示当前节点，findNode 用于查找当前节点之后的与当前节点值相同的节点。
// 当 nowNode 与 findNode 值不相等时，将 nowNode 移动到下一个节点。
// 当 nowNode 与 findNode 值相等时，使用 findNode 进行迭代查找，直到 findNode 的值与 nowNode 的值不相等或者 findNode 到达链表末尾。
// 将 nowNode 的 next 指向 findNode，即跳过所有与当前节点值相同的节点。
// 返回处理后的链表头节点。
static ListNode DeleteDuplicates4(ListNode head)
{
// 如果链表为空或只有一个节点，直接返回，因为不可能有重复节点
if (head == null || head.next == null) return head;
// 初始化两个指针，nowNode 表示当前节点，findNode 用于查找与当前节点值相同的节点
ListNode nowNode = head;
ListNode findNode = head;
// 遍历链表
while (nowNode.next != null)
{
// 如果当前节点和下一个节点的值不相等
if (nowNode.val != nowNode.next.val)
{
// 移动当前节点到下一个节点
nowNode = nowNode.next;
}
else
{
// 当前节点和下一个节点的值相等，使用 findNode 进行迭代查找
findNode = nowNode.next;
while (findNode.val == nowNode.val)
{
// 如果 findNode 的下一个节点不为空，继续向后查找
if (findNode.next != null)
{
findNode = findNode.next;
}
else
{
// 如果 findNode 到达链表末尾，则跳出循环
findNode = null;
break;
}
}
// 将当前节点的 next 指向 findNode，即跳过所有与当前节点值相同的节点
nowNode.next = findNode;
}
}
// 返回处理后的链表头节点
return head;
}
#endregion
#region 辅助方法
static void PrintList(string example, string method, ListNode input, ListNode output)
{
Console.Write($"{example} {method} 输入：[");
while (input != null)
{
Console.Write(input.val);
input = input.next;
if (input != null)
Console.Write(", ");
}
Console.Write("]\n");
Console.Write($"{example} {method} 输出：[");
while (output != null)
{
Console.Write(output.val);
output = output.next;
if (output != null)
Console.Write(", ");
}
Console.Write("]\n\n");
}
#endregion
}
83.4 运行结果
示例1 方法1 输入：[1, 2]
示例1 方法1 输出：[1, 2]
示例2 方法2 输入：[1, 1, 2, 3]
示例2 方法2 输出：[1, 2, 3]
示例3 方法3 输入：[1]
示例3 方法3 输出：[1]
示例4 方法4 输入：[1]
示例4 方法4 输出：[1]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
