题目描述

在一个排序的链表中，删除重复的节点。

解题思路:

1. 由于链表是排序的，可从头到尾遍历链表，如果当前节点A的值和下一个节点的值相同，则这个节点是可删除的，并再次从节点A开始遍历，把和A相同节点都删掉。
2. 需要注意的是，头节点也可能被删除。

代码

ListNode deleteDuplicate(ListNode head){
    if (head == null) {
        return null;
    }
    ListNode preNode = null;
    ListNode curNode = head;
    ListNode newHead = head; // 保存头节点
    while (curNode != null && curNode.next != null) {
        boolean needDel = false;
        if (curNode.value == curNode.next.value) {
            // 判断节点是否重复
            needDel = true;
        }
        if (needDel) {
            // 删除和当前节点值相同的所有节点
            String value = curNode.value;
            while (curNode!= null && curNode.value == value) {
                curNode = curNode.next;
            }
            if (preNode != null) {
                preNode.next = curNode;
            } else {
                preNode = curNode;
                newHead = preNode;
            }
        } else {
            if (preNode == null) {
                newHead = curNode;
            }
            preNode = curNode;
            curNode = curNode.next;
        }
    }
    return newHead;
}