删除排序链表重复元素
时间: 2024-07-21 13:00:46 浏览: 77
删除排序链表中的重复元素
删除排序链表中的重复元素是指在一个已排序的链表中,移除所有相邻的重复节点,使得每个节点的值都是其前一个节点值之后的第一个非重复值。例如,给定链表 `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 达到链表尾部。
阅读全文