22.链表中倒数最后k个结点.md

22.链表中倒数最后k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1

输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。

示例2

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

思路 & 解答

思路比较清晰，那就是前后双指针，先让第1个指针先走k步，然后第2个指针开始走，而且两个指针一起走，直到第一个指针走到最后的位置。

Java 代码实现如下：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k <= 0) {
            return null;
        }
        ListNode first = head;
        while (k != 0) {
            if (first == null) {
                return null;
            }
            first = first.next;
            k--;
        }
        while (first!= null) {
            head = head.next;
            first = first.next;
        }
        return head;
    }
}

C++ 代码实现如下：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        if (pHead == NULL || k <= 0) {
            return NULL;
        }
        ListNode *first = pHead;
        while (k != 0) {
            if (first == NULL) {
                return NULL;
            }
            first = first->next;
            k--;
        }
        while (first!= NULL) {
            pHead = pHead->next;
            first = first->next;
        }
        return pHead;
    }
};

时间复杂度：快指针走到末尾，O(n) 空间复杂度：没有借助额外的空间，为 O（1）