在单链表和双链表中删除倒数第 K 个节点

【题目】 分别实现两个函数，一个可以删除单链表中倒数第 K 个节点，另一个可以删除双链表中倒数第 K 个节点。 【要求】 如果链表长度为 N，时间复杂度达到 O(N)，额外空间复杂度达到 O(1)。

【解答】 本题较为简单，实现方式也是多种多样的，这里供一种方法供读者参考。 先来看看单链表如何调整。如果链表为空或者 K 值小于 1，这种情况下，参数是无效的，直接返回即可。

除此之外，让链表从头开始走到尾，每移动一步，就让 K 的值减 1。 链表：1->2->3，K = 4，链表根本不存在倒数第 4 个节点。 走到的节点：1 -> 2 -> 3 K 变化为：3 2 1 链表：1->2->3，K = 3，链表倒数第 3 个节点是 1 节点。 走到的节点：1 -> 2 -> 3 K 变化为：2 1 0 链表：1->2->3，K = 2，链表倒数第 2 个节点是 2 节点。 走到的节点：1 -> 2 -> 3

K 变化为：1 0 -1 由以上三种情况可知，让链表从头开始走到尾，每移动一步，就让 K 值减 1，当链表走到结尾时，如果 K 值大于 0，说明不用调整链表，因为链表根本没有倒数第 K 个节点，此时将原链表直接返回即可；

如果 K 值等于 0，说明链表倒数第 K 个节点就是头节点，此时直接返回head.next，也就是原链表的第二个节点，让第二个节点作为链表的头返回即可，相当于删除头节点；

接下来，说明一下如果 K 值小于 0，该如何处理。 先明确一点，如果要删除链表的头节点之后的某个节点，实际上需要找到要删除节点的前一个节点，比如：1->2->3，如果想删除节点 2，则需要找到节点 1，然后把节点 1 连到节点 3上（1->3），以此来达到删除节点 2 的目的。

如果 K 值小于 0，如何找到要删除节点的前一个节点呢？方法如下： 1．重新从头节点开始走，每移动一步，就让 K 的值加 1。 2．当 K 等于 0 时，移动停止，移动到的节点就是要删除节点的前一个节点。 这样做是非常好理解的，因为如果链表长度为 N，要删除倒数第 K 个节点，很明显，倒数第 K 个节点的前一个节点就是第 N-K 个节点。在第一次遍历后，K 的值变为 K-N。

第二次遍历时，K 的值不断加 1，加到 0 就停止遍历，第二次遍历当然会停到第 N-K 个节点的位置。 具体过程请参看如下代码中的 removeLastKthNode 方法。

public class RemoveLastKthNode {

    static class Link {
        private Node head = null;
        static class Node {
            private int value;
            private Node next;
            public Node(int value) {
                this.value = value;
            }
        }

        public void add(int value) {
            Node newNode = new Node(value);
            if (head == null) {
                head = newNode;
            } else {
                Node temp = head;
                while (temp.next != null) {
                    temp = temp.next;
                }
                temp.next = newNode;
            }
        }
    }

    public static Link.Node removeLastKthNode(Link.Node head, int k) {
        // 如果头节点为空或k < 1那参数没有意义
        if (head == null || k < 1) {
            return head;
        }

        // 从头节点开始向后遍历，每遍历一次k减1
        Link.Node cur = head;
        while (cur != null) {
            k--;
            cur = cur.next;
        }
        // 当遍历完链表k = 0时，说明k等于链表的长度，那么倒数第k个节点就是头节点
        if (k == 0) {
            return head.next;
        } else if (k > 0) { // 如果k > 0 说明k的值大于链表的长度
            return head;
        } else if (k < 0) { // 如果k < 0 说明存在倒数第k个节点
            // 从头节点开始遍历，每次加一，注意是先加一再比较
            cur = head;
            while (++k != 0) { //当k == 0时，不会进入循环，此时，cur 指向要删除节点的前一个节点
                cur = cur.next;
            }
            // 删除要删除的节点，改变指针指向即可
            cur.next = cur.next.next;
        }
        return head;
    }

    public static void main(String[] args) {
        Link link = new Link();
        link.add(1);
        link.add(2);
        link.add(3);
        link.add(4);
        link.add(5);

        removeLastKthNode(link.head, 2);

        while (link.head != null) {
            System.out.print(link.head.value + " ");
            link.head = link.head.next;
        }
    }
}

对于双链表的调整，几乎与单链表的处理方式一样，注意 last 指针的重连即可。具体过程请参看如下代码中的 removeLastKthDoubleNode 方法。

public class RemoveLastKthDoubleNode {

     class DoubleLink {
        private Node head = null;

        class Node {
            private int value;
            private Node next;
            private Node last;

            public Node(int value) {
                this.value = value;
            }
        }
    }

    public DoubleLink.Node removeLastKthDoubleNode(DoubleLink.Node head, int k) {
        if (head == null || k < 1) {
            return head;
        }

        DoubleLink.Node cur = head;
        while (cur != null) {
            k--;
            cur = cur.next;
        }
        if (k == 0) {
            head = head.next;
            head.last = null;
        } else if (k > 0) {
            return head;
        } else {
            cur = head;
            while (++k != 0) {
                cur = cur.next;
            }
            DoubleLink.Node newNode = cur.next.next;
            cur.next = newNode;
            if (newNode != null) {
                newNode.last = cur;
            }
        }
        return head;
    }
}