题目:给你一个整数数组 nums
和一个链表的头节点 head
。从链表中移除所有存在于 nums
中的节点后,返回修改后的链表的头节点。
思路:把数组元素放到set里,用set.contains判断,其他部分 按照模板写即可
代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
Set<Integer> set = new HashSet<>();
for (int num : nums)
set.add(num);
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null) {
int value = cur.next.val;
if (set.contains(value)) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
性能:
时间复杂度o(m+n)m链表长度 n是数组长度
空间复杂度o(n)