王俊超 · 更新于 2018-11-28 11:00:43

链表中倒数第 k 个结点

题目:输入一个链表,输出该链表中倒数第k 个结点.为了符合大多数人的习惯,本题从 1 开始计数,即链表的尾结点是倒数第 1 个结点.例如一个链表有 6 个结点,从头结点开始它们的值依次是 1 、2、3、4、5 、6。这个个链表的倒数第 3 个结点是值为 4 的结点。

链表结点定义如下:

public static class ListNode {
    int value;
    ListNode next;
}

解题思路:

为了实现只遍历链表一次就能找到倒数第 k 个结点,我们可以定义两 个指针。第一个指针从链表的头指针开始遍历向前走 k-1步,第二个指针保持不动;从第k 步开始,第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在 k-1 , 当第一个(走在前面的)指针到达链表的尾结点时,第二个指针(走在后面的)指针正好是倒数第 k 个结点。

代码实现:

public class Test15 {
    public static class ListNode {
        int value;
        ListNode next;
    }
    /**
     * 输入一个键表,输出该链表中倒数第k 个结点.为了符合大多数人的习惯,
     * 本题从1开始计数,即链表的尾结点是倒数第1个结点.例如一个链表有6个结点,
     * 从头结点开始它们的值依次是1、2、3、4、5 6。这个链表的倒数第3个结点是值为4的结点.
     *
     * @param head 链表的头结点
     * @param k    倒数第k个结点
     * @return 倒数第k个结点
     */
    public static ListNode findKthToTail(ListNode head, int k) {
        // 输入的链表不能为空,并且k大于0
        if (k < 1 || head == null) {
            return null;
        }
        // 指向头结点
        ListNode pointer = head;
        // 倒数第k个结点与倒数第一个结点相隔k-1个位置
        // pointer先走k-1个位置
        for (int i = 1; i < k; i++) {
            // 说明还有结点
            if (pointer.next != null) {
                pointer = pointer.next;
            }
            // 已经没有节点了,但是i还没有到达k-1说明k太大,链表中没有那么多的元素
            else {
                // 返回结果
                return null;
            }
        }
        // pointer还没有走到链表的末尾,那么pointer和head一起走,
        // 当pointer走到最后一个结点即,pointer.next=null时,head就是倒数第k个结点
        while (pointer.next != null) {
            head = head.next;
            pointer = pointer.next;
        }
        // 返回结果
        return head;
    }
    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.value = 1;
        head.next = new ListNode();
        head.next.value = 2;
        head.next.next = new ListNode();
        head.next.next.value = 3;
        head.next.next.next = new ListNode();
        head.next.next.next.value = 4;
        head.next.next.next.next = new ListNode();
        head.next.next.next.next.value = 5;
        head.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.value = 6;
        head.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.value = 7;
        head.next.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.next.value = 8;
        head.next.next.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.next.next.value = 9;
        System.out.println(findKthToTail(head, 1).value); // 倒数第一个
        System.out.println(findKthToTail(head, 5).value); // 中间的一个
        System.out.println(findKthToTail(head, 9).value); // 倒数最后一个就是顺数第一个
        System.out.println(findKthToTail(head, 10));
    }
}

运行结果: