思想: **
** 1.pHead为null或者pHead.next==null,返回pHead。
* 2.否则,初始化pre和itr,pre指向pHead,pHead指向itr,以方便可以同时删除多个重复的节点(中间始终隔了一个节点),初始化flag标记itr前一个节点是否是重复节点。*
* 3.如果当前遍历节点和前面一个节点重复,标记位flag为true,当前节点itr后移,后移的同时判断是否到结尾,到结尾pre指向itr.*
* 4.如果遇到当前节点和前面不等,如果flag为true(前一节点是重复点),pre跳过前面 节点指向itr,itr后移。*
* 5.否则前面节点不是重复节点,pre后移,itr后移*
* 时间复杂度:O(N),空间复杂度O(1)*
//时间复杂度O(N),空间O(1)
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead==null||pHead.next==null)
return pHead;
ListNode pre_head = new ListNode(-1);
pre_head.next=pHead;
ListNode pre = pre_head;
ListNode itr = pHead.next;
boolean flag = false;
while(itr!=null){
if(pre.next.val==itr.val){
flag=true;
itr=itr.next;
if(itr==null)//如果到最后,不加此语句,最后相同数的不会被消除
pre.next=itr;
continue;
}
if(flag)
pre.next=itr;
else{
pre=pre.next;
}
itr=itr.next;
flag=false;//上一段相同的结束
}
// if(all)return null;
return pre_head.next;
}
}
京公网安备 11010502036488号