[数据结构与算法]【链表】剑指offer 22. 链表中倒数最后k个结点

题目

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，输出一个链表，该输出链表包含原链表中从倒数第 k 个结点至尾节点的全部节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：$0<n<10^5$ ，$0\le a_i\le 10^9$ ，$0\le k\le 10^9$

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
示例1

输入：
{1,2,3,4,5},3
返回值：
{3,4,5}

示例2

输入：
{2},8
返回值：
{}

方法

baseline

最简单的方法，先遍历一遍链表，统计链表元素个数n，然后再遍历一次链表，返回n-k位置的指针。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param pHead ListNode类
     * @param k     int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail(ListNode pHead, int k) {
        // write code here
        ListNode tmp = pHead;
        int count = 0; // 统计链表的长度
        while (true) {
            if (tmp != null) {
                count++;
                tmp = tmp.next;
            } else
                break;
        }
        if (k > count)
            return null;
        tmp = pHead;
        for (int i = 0; i < count - k; i++)
            tmp = tmp.next;
        return tmp;
    }
}

快慢指针法

使用两个指针fast和slow，先让fast走k步，然后fast和slow一起往后走，直到fast到达尾部，此时slow就处于倒数第k个位置，直接返回slow即可。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param pHead ListNode类
     * @param k     int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail(ListNode pHead, int k) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        for (int i = 0; i < k; i++) {
            if (fast != null) fast = fast.next;
            else return null;
        }
        while (true) {
            if (fast != null) {
                fast = fast.next;
                slow = slow.next;
            } else break;
        }
        return slow;
    }
}