博客

package com.niuke;

/**
 * Created by admin on 2018/3/11.
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，
 * 返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 *  public class ListNode {
 int val;
 ListNode next = null;

 ListNode(int val) {
 this.val = val;
 }
 }
 */
public class DeleteDuplication {
    public ListNode deleteDuplication(ListNode pHead)
    {
        //1 递归
        if(pHead==null||pHead.next==null) {//只有0个或者1个节点 ，返回
            return pHead;
        }
        if(pHead.val==pHead.next.val) {//如果当前节点是重复节点
            ListNode pNode=pHead.next;
            while (pNode!=null&&pNode.val==pHead.val) {
                //找到第一个与当前节点不相同的节点
                pNode=pNode.next;
            }
            return deleteDuplication(pNode);//从第一个与当前结点不同的结点开始递归
        } else {//如果当前节点不是重复节点
            pHead.next=deleteDuplication(pHead.next);//保留当前结点，从下一个结点开始递归
            return pHead;
        }
    }

    //2 用指针 把当前节点的前一节点(pre)指向当前节点的后一节点
    public ListNode deleteDuplication2(ListNode pHead) {
        if(pHead==null||pHead.next==null) {//只有0个或者1个节点 ，返回
            return pHead;
        }
        ListNode tmp=new ListNode(-1);//设置前一节点的初始值
        tmp.next=pHead;//将前一节点指向头结点
        ListNode curNode=pHead;//当前节点
        ListNode pre=tmp;//当前节点的前一节点
        while (curNode!=null&&curNode.next!=null) {
            ListNode next=curNode.next;
            if(curNode.val==next.val) {//当前节点是重复值
                while (next!=null&&curNode.val==next.val) {
                    next=next.next;
                }
                pre.next=next;//前一节点指向去重之后的节点
                curNode=next;//去重之后的节点变为当前节点
            } else {//当前节点不是重复值
                pre=curNode;//当前节点变为前一节点
                curNode=curNode.next;//当前节点向后移
            }
        }
        return tmp.next;
    }
}