给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 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;
}
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;
}
评论