删除排序链表重复元素
时间: 2024-07-21 16:00:46 浏览: 55
删除排序链表中的重复元素是指在一个已排序的链表中,移除所有相邻的重复节点,使得每个节点的值都是其前一个节点值之后的第一个非重复值。例如,给定链表 `1->1->2->3->3`,应该变成 `1->2->3`。
一种常见的解决方案是使用两个指针,一个快指针(f)和一个慢指针(s)。首先,让快指针先遍历链表,每次移动两步;而慢指针每次只移动一步。这样,当快指针遇到重复节点时,慢指针还在原地,即找到重复开始的位置。然后,我们只需要将慢指针指向的节点设置为下一个不重复节点,并更新慢指针继续遍历即可。
下面是步骤总结:
1. 初始化两个指针 f 和 s 为链表头节点。
2. 当 f 遇到重复节点时(f.val == s.val),跳过 f,让它前进两步(f = f.next.next)。
3. 当 f 指向的节点不再重复时,将 s 的 next 指向该节点(s.next = f),然后同时移动 s(s = s.next)。
4. 重复步骤 2 和 3,直到 f 达到链表尾部。
相关问题
java单趟基数排序 链表
基数排序是一种非比较性的排序算法,通过将待排序的数字按照个位、十位、百位等位数进行排序,最终得到有序的结果。在使用链表来实现单趟基数排序时,可以按照以下步骤进行操作:
1. 创建一个链表数组,用于存储待排序数字。链表数组的数量应当等于基数的个数,例如十进制的基数排序需要创建10个链表。
2. 将待排序的数字按照个位数的值分别放入对应的链表中。为了实现这一步,可以从头到尾遍历待排序数字的链表,取每一个数字的个位数,然后根据个位数的值将数字插入到相应的链表中。如果数字的个位数为3,则将其插入到第4个链表中(下标从0开始)。
3. 依次遍历链表数组,将每一个链表中的元素重新按照十位数的值重新放入对应的链表中。这一步的操作与第2步类似,只是将个位数改为十位数。
4. 重复步骤3,直到最高位数的值得链表中没有数字。
5. 最后按照从低位到高位的顺序,依次遍历链表数组,将每一个链表中的元素依次取出,得到有序的结果。
使用链表来实现单趟基数排序的好处是可以节省空间,因为链表可以动态地分配内存,而不需要预先确定数字的个数。同时,链表的插入和删除操作比较高效,可以有效地进行大量数据的排序。另外,链表还可以很好地处理相同数字的情况,因为相同数字会被放入同一个链表中。但是使用链表实现的单趟基数排序算法需要设计合适的数据结构和算法来实现链表的排序和合并,以及数字的位置移动等操作。
CShap 已排序的链表中删除重复项 源代码
以下是C#中已排序的链表中删除重复项的源代码:
```
public ListNode DeleteDuplicates(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode current = head;
while (current != null && current.next != null)
{
if (current.val == current.next.val)
{
current.next = current.next.next;
}
else
{
current = current.next;
}
}
return head;
}
```
在这个方法中,我们首先检查链表是否为空或只有一个元素。如果是这样,我们返回原始链表。然后,我们定义一个当前节点变量,并将其设置为链表的头部。
我们使用 while 循环遍历链表,如果当前节点的值与下一个节点的值相同,则我们将当前节点的下一个节点指向下一个节点的下一个节点。否则,我们将当前节点移动到下一个节点。
最后,我们返回链表的头部。