一、删除链表节点

例：1->2->3->4->5

思路：假如要删除节点3，常规思路是遍历链表，当遍历到节点2的时候，发现节点2的 next是节点3，然后将将节点2的next指向节点4。时间复杂度是O(n)。

换一种思路当遍历到要删除的节点3时，将节点3的next也就是节点4的值赋值给节点3。然后删除节点4。假如要删除尾节点依然需要遍历链表找到尾节点删除。平均时间复杂度为O(1)。

public ListNode deleteNode(ListNode head, ListNode deleteNode) {

        if (head == null || deleteNode == null) {
            return null;
        }
        // 删除的不是尾节点
        if (deleteNode.next != null) {
            ListNode next = deleteNode.next;
            deleteNode.val = next.val;
            deleteNode.next = next.next;
            next = null;
        } else if (deleteNode == head) { //只有一个节点
            deleteNode = null;
            head = null;
        } else { // 链表是尾节点
            ListNode node = head;
            while (node.next != deleteNode) {
                node = node.next;
            }
            node.next = null;
            deleteNode = null;
        }
        return head;
    }
复制代码

二、删除链表的重复节点

例如：1->2->3->3->4->4->5

思路：创建一个虚拟头节点，用来操作头节点就是重复的情况，设置pre ，last 指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，向后搜索重复节点。

public ListNode deleteDuplication(ListNode pHead) {
        // 没有节点或者节点为null
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        // 创建一个头节点，用来方便操作头节点重复的情况
        ListNode virtualHead = new ListNode(-99);
        virtualHead.next = pHead;

        // 两个指针
        ListNode pre = virtualHead;
        ListNode last = pHead;
        while (last != null) {
            // 找到最后一个相同的节点
            if (last.next != null && last.val == last.next.val) {
                while (last.next != null && last.val == last.next.val) {
                    last = last.next;
                }
                pre.next = last.next;
                last = last.next;
            } else {
                pre = pre.next;
                last = last.next;
            }
        }

        return virtualHead.next;

    }
复制代码

三、寻找链表的倒数第K个节点

例如：1->2->3->4->5->6

思路：如果可以用额外的空间，那我们可以把链表节点都压入栈里，然后回溯除第k个节点就可以了。

还有一种思路就是求倒数第k个节点，就是求第n-k+1个节点。创建两个指针，第一个指针先从头往后走k-1步，第二个指针不动。如果第k-1个节点不存在，证明倒数第k个节点不存在。从第k步开始，两个指针一起向后移动，当第一个指针遍历到最后的时候第二个指针就是倒是第k个节点。

public ListNode findKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode k1 = head;
        ListNode k2 = head;

        for (int i = 0; i < k - 1; i++) {
            if (k1.next == null) {
                return null;
            } else {
                k1 = k1.next;
            }
        }
        while (k1.next != null) {
            k1 = k1.next;
            k2 = k2.next;
        }
        return k2;
    }
复制代码

。。。。持续更新中