低调做个路人
2020-04-01 17:55:59
398
82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
思路一：使用map记录节点值将所有出现次数大于1的值删除。需要遍历两次并且使用散列表辅助空间。
ListNode deleteDuplicates(ListNode head) {
Map<Integer,Boolean> map=new HashMap<>();
ListNode tem=head;
while(tem!=null){
if(map.containsKey(tem.val)){
map.put(tem.val,true);
}else{
map.put(tem.val,false);
}
tem=tem.next;
}
ListNode node=new ListNode(0);
node.next=head;
ListNode res=node;
while(node.next!=null){
if(map.get(node.next.val))
{
node.next=node.next.next;
}else {
node=node.next;
}
}
return res.next;
}执行用时 :5 ms, 在所有 java 提交中击败了5.79%的用户
内存消耗 :36.6 MB, 在所有 java 提交中击败了62.44%的用户
嗯。。。慢的一批。。尝试其他思路。。
思路二：对于每一个节点比较 它后面两个元素是否相等，如果相等继续判断第三，四，五...个是否相等，然后删除这些节点。如果不相等，往后遍历。
public ListNode deleteDuplicates(ListNode head) {
ListNode lshead = new ListNode(0);//接一个头结点
lshead.next = head;
ListNode tem = lshead;//正在遍历的节点
ListNode prenode = tem.next;//遍历节点的后继
ListNode nextnode = null;//遍历节点的后继的后继
if (prenode != null) {
nextnode = prenode.next;
}
while (prenode != null && nextnode != null) {
while (nextnode != null&&prenode.val == nextnode.val) {//相等则nextnode继续往后遍历
nextnode = nextnode.next;
tem.next = nextnode;
}
if(nextnode!=null){//删除重复节点
prenode = tem.next;
nextnode = prenode.next;
}
while (nextnode != null && prenode.val != nextnode.val) {//不相等往后遍历
tem = tem.next;
prenode = tem.next;
nextnode = tem.next.next;
}
}
return lshead.next;
}执行用时 :1 ms, 在所有 java 提交中击败了98.53%的用户
内存消耗 :36.9 MB, 在所有 java 提交中击败了59.25%的用户
评论