题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
题目分析
我开始觉得问题很简单,只需要把重复部分的next交换即可。。后面做起来搞了很久。。。
问题1:如何判断返回后的头指针。 比如 1-1-1-2-2-2-3-4 最后实际返回的head为3。 我的解决办法是新增加一个头结点。看题目意思设为-1即可。为了严谨,设置为Integer.MAX_VALUE似乎最好了。。
问题2:如何去重。这部分常规做法:例如 1->2->3->3->4->4->5 比如两个指针pre指向2,cur指向3,判断cur与cur.next的值(while(cur.val == cur.next.val) 如果重复就后移。跳出循环是正好是cur(3节点)3 --> 4 cur.next(4节点)所以再后一位,pre继续为2,cur为4继续判断。。
代码
public ListNode deleteDuplication(ListNode pHead) { if(pHead == null){ return pHead; } //新增头结点。 ListNode head = new ListNode(Integer.MAX_VALUE); //链接头结点与题目的节点 head -> pHead head.next = pHead; //设置pre 和 cur 指针。 ListNode pre = head; ListNode cur = pre.next; //遍历链表结束跳出 while(cur!= null){ if(cur.next == null){ //防止空指针异常 return head.next; }else if(cur.next.val != cur.val){ // 不重复 pre、cur后移 pre = cur; cur= cur.next; }else{ while(cur.val == cur.next.val){ //重复 cur= cur.next; if(cur.next == null){ //防止空指针异常,如果跳转到结尾,直接pre --> null 返回即可 pre.next = null; return head.next; } } //从上面cur.val == cur.next.val的条件下跳出,所以cur为重复的值,需要跳过 cur= cur.next; pre.next = cur; // pre -- > cur } } return head.next; }