题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表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;
    }