删除链表的节点

题目：给定单向链表的头指针和一个节点指针，定义一个函数在 #card=math&code=O%281%29) 时间内删除该节点。

常规我们删除节点是从头节点开始遍历，找到要删除的节点，然后删除它。之所以要从头结点开始，是因为我们要找到该节点的前一个节点，然后才能删除该节点，有如下链表

比如我们要删除节点 3，这个时候我们必须找到它的前一个节点 2，将节点 2 的下一个指针指向节点 3 的下一个节点，如下

但是从头结点开始查找的话，它的时间复杂度就是 #card=math&code=O%28n%29)，达不到题目所要求的 #card=math&code=O%281%29) 的时间复杂度，这个时候我们就要另辟蹊径了。还是以删除节点 3 为例，这个时候可以将它下一个节点的值覆盖要被删除节点的值，即用 4 覆盖 3，然后删除节点 4，因为我们知道节点 4 的前一个节点(即给定的要删除的节点)，所以可以将节点 4 删除，如下

这时我们不用从头结点进行遍历，所需要的复杂度是 #card=math&code=O%281%29)。

但是事情到这里还没有完成，如果要删除的节点是最后一个节点呢? 这个时候它没有下一个节点，我们就不得不从头结点开始遍历来删除这个节点了，这个时候就得知道它的前一个节点。这里又要考虑一种情况，因为要知道尾结点的前一个节点，如果链表只有一个元素的话，尾结点就没有前一个节点，这种情况要做特殊处理。代码如下：

public class DeleteNode {
    private static class ListNode {
        ListNode next;
        int value;
        public ListNode(int value) {
            this.value = value;
            this.next = null;
        }
    }
    public static ListNode deleteNode(ListNode root, ListNode toBeDeletedNode) {
        if (root == null || toBeDeletedNode == null) {
            return root;
        }
        // 如果不是尾结点
        if (toBeDeletedNode.next != null) {
            // 将后面节点的值覆盖要删除的节点的值
            toBeDeletedNode.value = toBeDeletedNode.next.value;
            // 删除下一个节点
            ListNode deleteNext = toBeDeletedNode.next;
            toBeDeletedNode.next = deleteNext.next;
            deleteNext = null;
        } else {
            // 被删除的节点是尾结点
            ListNode cur = root;
            // 同时被删除的节点也是头结点，即只有一个元素
            if (cur == toBeDeletedNode) {
                root = null;
                toBeDeletedNode = null;
                return root;
            }
            // 从头结点遍历找到前一个节点
            while(cur.next != toBeDeletedNode) {
                cur = cur.next;
            }
            cur.next = null;
            toBeDeletedNode = null;
        }
        return root;
    }
    // 打印链表的方法
    public static void printList(ListNode root) {
        while (root != null) {
            if (root.next != null) {
                System.out.print(root.value + "->");
            } else {
                System.out.println(root.value);
            }
            root = root.next;
        }
    }
    // 测试代码
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next = new ListNode(2);
        root.next.next = new ListNode(3);
        root.next.next.next = new ListNode(4);
        root.next.next.next.next = new ListNode(5);
        printList(root); // 1->2->3->4->5
        root = deleteNode(root, root.next.next.next.next);
        printList(root); // 1->2->3->4
        root = deleteNode(root, root);
        printList(root); // 2->3->4
        root = deleteNode(root, root.next);
        printList(root); // 2->4
        root = deleteNode(root, root.next);
        printList(root); // 2
        root = deleteNode(root, root);
        printList(root); // 
    }
}

题目：在一个排序的链表中，如何删除重复的节点?

这道题仔细一想的话非常简单，因为这个链表是有序的，这就意味着重复的节点是连在一起的，所以我们只要比较当前节点与下一个节点的值是否相同，如果相同，则删除下一个节点，如果不同则移动当前节点到下一个节点，代码如下：

public class DeleteDuplicationNode {
    private static class ListNode {
        ListNode next;
        int value;
        public ListNode(int value) {
            this.value = value;
            this.next = null;
        }
    }
    public static void deleteDuplicationNode(ListNode root) {
        if (root == null) {
            return;
        }
        ListNode cur = root;
        while(cur.next != null) {
            // 如果当前节点的值与下一个节点的值相同，删除下一个节点
            if (cur.value == cur.next.value) {
                ListNode curNext = cur.next;
                cur.next = curNext.next;
                curNext = null;
            } else {
                // 否则移动当前节点
                cur = cur.next;
            }
        }
    }
    // 打印链表
    public static void printList(ListNode root) {
        while (root != null) {
            if (root.next != null) {
                System.out.print(root.value + "->");
            } else {
                System.out.println(root.value);
            }
            root = root.next;
        }
    }
    public static void main(String[] args) {
        ListNode root = new ListNode(1);
        root.next = new ListNode(1);
        root.next.next = new ListNode(2);
        root.next.next.next = new ListNode(2);
        root.next.next.next.next = new ListNode(2);
        root.next.next.next.next.next = new ListNode(3);
        printList(root); // 1->1->2->2->2->3
        deleteDuplicationNode(root); // 1->2->3
        printList(root);
    }
}