18_删除链表中重复的节点

题目1：在O(1)的时间内删除链表的节点
题目2：删除链表中重复的节点
要求1：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
要求2：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：建立辅助头结点，并把pre指向辅助头结点，cur指向头节点

// 定义结点结构
class ListNode1{
    int value;
    ListNode1 next;
    ListNode1(){};
    ListNode1(int value){
        this.value = value;
    }
}
class List{
    ListNode1 head = null;
    // 添加节点
    public void addNode(int val){
        ListNode1 node = new ListNode1(val);
        if(head == null){
            head = node;
            return;
        }
        ListNode1 temp = head;
        while(temp.next!=null){
            temp = temp.next;
        }
        temp.next = node;
    }
    // 遍历
    public void showList(){
        ListNode1 temp = head;
        while(temp!=null){
            System.out.println(temp.value);
            temp = temp.next;
        }
    }
    // 删除节点
    public void deleteNode(int value){
        if(head == null){
            return;
        }
        ListNode1 temp = head;
        // 如果要删除的节点在第一个节点
        if(temp.value == value){
            head = temp.next;
            return;
        }
        ListNode1 pre = null;
        while(temp!=null){
            if(temp.value == value){
                pre.next = temp.next;
                return;
            }
            pre = temp; // pre指向temp前一个节点
            temp = temp.next;
        }
    }
    // 删除重复节点方法一，注意头节点重复的情况
    public ListNode1 DeleteDuplication(){
        if(head == null){
            return head;
        }
        ListNode1 preNode = null;
        ListNode1 tempNode = head;

        while(tempNode != null){
            if(tempNode.next !=null && tempNode.value == tempNode.next.value){  // 注意要加上tempNode != null，不然会出错
                while(tempNode.next !=null && tempNode.value == tempNode.next.value){
                    tempNode = tempNode.next;
                }
                // 如果要删除的节点在第一个节点
                if(head.next.value == head.value){
                    head =tempNode.next;
                }else{
                    preNode.next = tempNode.next;
                }
                tempNode = tempNode.next;
            }else{
                preNode = tempNode;
                tempNode = tempNode.next;
            }
        }
        return head;
    }
    // 删除重复节点方法二，建立辅助头结点，并把pre指向辅助头结点，cur指向头节点
    public ListNode1 DeleteDuplication01(){
        if(head == null || head.next == null){
            return head;
        }
        // 自己构建辅助头结点
        ListNode1 h = new ListNode1(Integer.MIN_VALUE);
        h.next = head;
        ListNode1 pre = h;
        ListNode1 cur = h.next;
        while(cur!=null){
            if(cur.next != null && cur.next.value == cur.value){
                // 相同结点一直前进
                while(cur.next != null && cur.next.value == cur.value){
                    cur = cur.next;
                }
                // 退出循环时，cur 指向重复值，也需要删除，而 cur.next 指向第一个不重复的值
                // cur 继续前进
                cur = cur.next;
                // pre 连接新结点
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return h.next;
    }
    // O(1)时间删除节点
    public void deleteNode01(ListNode1 toBeDeleted){
        if (head == null || toBeDeleted == null) {
            return;
        }
        // 删除的结点不是尾结点
        if (toBeDeleted.next != null) {
            toBeDeleted.value = toBeDeleted.next.value;
            toBeDeleted.next = toBeDeleted.next.next;
            // 删除结点为头结点
        } else if (head == toBeDeleted) {
            head = null;
            // 删除结点为尾结点
        } else {
            ListNode1 temp = head;
            // 定位到要删除节点的前一节点
            while (temp.next != toBeDeleted) {
                temp = temp.next;
            }
            temp.next = null;
        }
    }

}
public class L18_DeleteNode {
    public static void main(String[] args) {
        List listNode = new List();
        listNode.addNode(1);
        listNode.addNode(1);
        listNode.addNode(2);
        listNode.addNode(2);
        listNode.addNode(2);
//        listNode.deleteNode(3);
        listNode.DeleteDuplication();
//        listNode.DeleteDuplication01();
        listNode.showList();
    }
}