链表中倒数第k个节点

题目描述

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

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.  
返回链表 4->5.

题目链接

Leetcode

题目解答

这个题目的思路是比较清晰的，使用快慢指针，开始的时侯让快指针p1先走k步，然后慢指针p2和快指针同时向后移动，当快指针p1运动到链表尾部的时侯，返回慢指针p2指向的节点即可。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p1 = head, p2 = head;
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.2 MB, 在所有 Java 提交中击败了79.12%的用户

需要注意的地方是题目给的测试用例没有包含超出链表长度范围的用例，对于这种情况可以在快指针p1移动过程中进行判断，如果快指针移动的过程中已经到达了链表末尾，则直接返回空，这部分代码如下。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p1 = head, p2 = head;
        for (int i = 0; i < k; i++) {
            // 增加非空判断
            if (p1 == null) {
                return null;
            }
            p1 = p1.next;
        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }
}