链表中倒数第k个节点

关键词：链表

题目描述

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

示例 1：

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

思路

思路一：

利用快慢指针

1.快指针和慢指针相差k

2.快指针到达链尾，慢指针所指方向就是倒数第k个链表

代码

思路一：

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* cur = head;
        for(int i = 0; i < k; i ++) cur = cur->next;
        while(cur) {
            cur = cur->next;  //快指针
            head = head->next;  //慢指针
        }
        return head;
    }
};

知识点

1. 快慢指针的使用；
2. 可以用while(cur)来直接判断是否跳出循环。