AcWing 33：链表中倒数第k个节点 ← 尾插法

【题目来源】
https://www.acwing.com/problem/content/32/

【题目描述】
输入一个链表，输出该链表中倒数第 k 个结点。

注意：
    ● k >= 1;
    ● 如果 k 大于链表长度，则返回 NULL；

【数据范围】
链表长度 [0,30]。

【输入样例】
输入：链表：1->2->3->4->5 ，k=2

【输出样例】
输出：4

【算法分析】
● 假设链表有 n 个结点，那么只要从头结点开始往后走 n-k 步就可以到达倒数第 k 个结点（从 1 开始计数）。
● 头插法及尾插法
头插法创建单链表：https://blog.csdn.net/hnjzsyjyj/article/details/120285274
尾插法创建单链表：https://blog.csdn.net/hnjzsyjyj/article/details/120285300
本题算法，选用尾插法建立单链表。
● ​​​​​​​适应本例类风格的代码如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    public:
        ListNode* findKthToTail(ListNode* head, int k) {
            int cnt=0;
            ListNode* p=head;
            while(p) {
                cnt++;
                p=p->next;
            }

            if(cnt<k) return NULL; //nullptr

            p=head;
            for(int i=0; i<cnt-k; i++) p=p->next;
            return p;
        }
};

【利用尾插法构建单链表后求解的完整代码】

#include <bits/stdc++.h>
using namespace std;

struct LNode {
    int data;
    LNode *next;
};
typedef struct LNode *LinkList;

void Tail_Insert(LinkList &L) {
    L=new LNode;
    L->next=NULL;
    LinkList r=L;

    printf("Input value:");
    int x;
    while(scanf("%d",&x)!=EOF) {
        LinkList p;
        p=new LNode;
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

void findKthToTail(LinkList &L,int k) {
    LinkList tail=L, head=L;
    if(k<=0) {
        printf("Input error!\n");
        return;
    }

    for(int i=1; i<=k; i++) {
        tail=tail->next;
        if(tail==NULL) {
            printf("No such node!\n");
            return;
        }
    }

    while(tail!=NULL && head!=NULL) {
        tail=tail->next;
        head=head->next;
    }
    printf("%d\n",head->data);
}

int main() {
    int k;
    LinkList L=new LNode;
    L->next=NULL;

    Tail_Insert(L);

    printf("Input k:");
    while(scanf("%d",&k)!=EOF) {
        findKthToTail(L,k);
        printf("Input k:");
    }
    return 0;
}


/*
Input value:9 6 2 8 5
^Z
Input k:3
2
Input k:2
8
Input k:5
9
Input k:1
5
Input k:12
No such node!
Input k:-12
Input error!
Input k:
*/

【参考文献】
https://blog.csdn.net/zwb8848happy/article/details/7330586
https://www.acwing.com/video/2698/