写一算法代码,将单链表中值重复的结点删除,使所得的结果链表中所有结点的值均不相同。
时间: 2024-09-14 13:12:51 浏览: 49
为了删除单链表中值重复的节点,我们可以遍历链表,同时使用一个哈希表来记录已经出现过的值。具体步骤如下:
1. 初始化一个空的哈希表用于记录已经出现过的节点值。
2. 创建一个虚拟头节点(dummy head),它是一个指向链表头节点的节点,这样可以简化边界条件的处理。
3. 遍历原链表,对于当前遍历到的节点,检查其值是否已经在哈希表中:
- 如果已经存在,则表示该值重复,需要删除当前节点,并将下一个节点连接到前一个节点上。
- 如果不存在,则将当前节点值添加到哈希表中,并继续遍历。
4. 由于我们无法通过尾部删除节点,我们需要在删除节点后,将当前节点指向下下个节点,而不是直接删除节点。
5. 最终返回虚拟头节点的下一个节点,即为去重后的链表头节点。
以下是算法的伪代码实现:
```
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0); // 创建虚拟头节点
dummy.next = head;
ListNode current = head;
Set<Integer> seen = new HashSet<>();
while (current != null && current.next != null) {
if (seen.contains(current.next.val)) {
// 如果当前节点的下一个节点值已经出现过,删除该节点
current.next = current.next.next;
} else {
// 如果未出现过,将该值加入到已见过的集合中,并移动当前节点
seen.add(current.val);
current = current.next;
}
}
return dummy.next;
}
```