面试题18：删除链表的节点

题目：在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点，链表节点与函数的定义如下：

class ListNode{
    int value;
    ListNode next;
}
public void deleteNode(ListNode head, ListNode toBeDeleted);

思路：充分利用节点里面next这个参数，如果要删除i，则先把i之后的节点j的值复制给节点i，然后把节点i的next指向j的next，最后删除节点j。注意，这里要考虑到链表只有一个节点和待删除的节点位于链表末的情况。
解决方案：

public class Question18 {
    static class ListNode{
        public ListNode(int value){
            this.value = value;
        }
        int value;
        ListNode next;
    }

    public static void deleteNode(ListNode head, ListNode toBeDeleted){
        if (head == null || toBeDeleted == null) return;
        // 要删除的节点的next节点存在
        if (toBeDeleted.next != null){
            ListNode next = toBeDeleted.next;
            toBeDeleted.value = next.value;
            toBeDeleted.next = next.next;
        }
        // 删除的节点的next节点不存在
        else {
            ListNode node = head;
            while (node.next != toBeDeleted){
                node = node.next;
            }
            node.next = null;
        }
    }
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode pAhead = new ListNode(3);
        ListNode pBhead = new ListNode(5);
        ListNode pChead = new ListNode(7);
        pHead.next = pAhead;
        pAhead.next = pBhead;
        pBhead.next = pChead;
        deleteNode(pHead, pBhead);
        while (pHead != null) {
            System.out.print(pHead.value + ",");
            pHead = pHead.next;
        }
    }
}

题目：在一个排序的链表中，删除链表中重复的节点。
思路：通过pre、node和needDelete来控制，如果有重复元素，则needDelete设置为true，然后把pre的next设置为node的next的next，并且刷新node为node的next的next。
解决方案：

public class Question18 {
    static class ListNode{
        public ListNode(int value){
            this.value = value;
        }
        int value;
        ListNode next;
    }
    public static void deleteDuplication(ListNode head){
        if (head == null) return;
        ListNode pre = new ListNode(Integer.MIN_VALUE);
        ListNode node = head;
        boolean needDelete = false;
        while (node != null){
            ListNode next = node.next;
            if (next != null && next.value == node.value){
                needDelete = true;
            }

            if (!needDelete){
                pre = node;
                node = node.next;
            }else {
                pre.next = node.next.next;
                node = node.next.next;
                needDelete = false;
            }
        }
    }

    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode pAhead = new ListNode(3);
        ListNode pBhead = new ListNode(5);
        ListNode pChead = new ListNode(5);
        pHead.next = pAhead;
        pAhead.next = pBhead;
        pBhead.next = pChead;
//        deleteNode(pHead, pBhead);
        deleteDuplication(pHead);
        while (pHead != null) {
            System.out.print(pHead.value + ",");
            pHead = pHead.next;
        }
    }
}