写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。用Java写
时间: 2024-09-18 18:14:51 浏览: 54
删除单链表中值相同的多余结点的算法
要解决这个问题,我们可以遍历链表并维护一个哈希集合(HashSet),用于跟踪已经遇到过的元素。如果当前节点的值已经在哈希集中,说明它是重复的,我们就删除该节点;否则,将它添加到哈希集中,并继续遍历。
以下是使用Java实现的一个简单算法:
```java
import java.util.HashSet;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode removeDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
HashSet<Integer> set = new HashSet<>();
ListNode current = head;
while (current != null) {
if (!set.add(current.val)) {
// 如果当前节点值已存在,则删除它
ListNode temp = current.next;
current.next = current.next.next;
current = temp;
} else {
current = current.next;
}
}
return head;
}
```
这个函数会返回一个新的链表,其中每个值都是唯一的。如果原链表中有重复的值,它们都会被从新链表中移除。
阅读全文