java 9名同学分别写下自己的幸运数字,并按数字从小到大存储到链表中。小明想 知道这9名同学的幸运数字有哪几个,并想删除初始链表中重复的幸运数字。请你设计编程算法,帮助小 明实现这一功能。需要注意的是:若头节点或头节点的下一个节点为空,则返回头节点。
时间: 2023-05-18 14:07:37 浏览: 110
以下是一个可能的 Java 算法实现:
```java
import java.util.HashSet;
public class LuckyNumbers {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public static ListNode removeDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
HashSet<Integer> set = new HashSet<>();
set.add(head.val);
ListNode prev = head;
ListNode curr = head.next;
while (curr != null) {
if (set.contains(curr.val)) {
prev.next = curr.next;
} else {
set.add(curr.val);
prev = curr;
}
curr = curr.next;
}
return head;
}
public static void main(String[] args) {
ListNode head = new ListNode(3);
head.next = new ListNode(1);
head.next.next = new ListNode(7);
head.next.next.next = new ListNode(5);
head.next.next.next.next = new ListNode(3);
head.next.next.next.next.next = new ListNode(2);
head.next.next.next.next.next.next = new ListNode(7);
head.next.next.next.next.next.next.next = new ListNode(8);
head.next.next.next.next.next.next.next.next = new ListNode(1);
head = removeDuplicates(head);
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
}
}
```
这个算法使用了一个 HashSet 来存储已经出现过的幸运数字,然后遍历链表,如果当前节点的值已经在 HashSet 中出现过了,就删除当前节点,否则将当前节点的值加入 HashSet 中。最后返回头节点即可。
注意,这个算法的时间复杂度是 O(n),其中 n 是链表的长度,因为需要遍历整个链表一次。空间复杂度也是 O(n),因为需要使用一个 HashSet 来存储已经出现过的幸运数字。
阅读全文