输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。c 语言

struct ListNode {
int val;
struct ListNode *next;
};

struct ListNode* findKthToTail(struct ListNode* head, int k) {
if (head == NULL || k <= 0) {
return NULL;
}
struct ListNode* p1 = head;
struct ListNode* p2 = head;
// p2先向后移动k-1个结点
for (int i = 0; i < k - 1; i++) {
if (p2->next != NULL) {
p2 = p2->next;
} else {
// k大于链表长度
return NULL;
}
}
// p1和p2一起向后移动，直到p2到达链表尾部
while (p2->next != NULL) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}

相关问题

用C语言输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* createList(int n) { // 创建链表
    struct ListNode *head = NULL;
    struct ListNode *tail = NULL;
    for (int i = 1; i <= n; i++) {
        struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = i;
        node->next = NULL;
        if (head == NULL) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }
    return head;
}

struct ListNode* findKthFromEnd(struct ListNode* head, int k) { // 查找倒数第k个节点
    struct ListNode *p1 = head;
    struct ListNode *p2 = head;
    for (int i = 0; i < k; i++) {
        if (p2 == NULL) {
            return NULL;
        }
        p2 = p2->next;
    }
    while (p2 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

void printList(struct ListNode *head) { // 遍历链表并输出
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n");
}

int main() {
    int n, k;
    printf("请输入链表长度n和倒数第k个结点：");
    scanf("%d %d", &n, &k);
    struct ListNode *head = createList(n);
    printf("链表为：");
    printList(head);
    struct ListNode *node = findKthFromEnd(head, k);
    if (node == NULL) {
        printf("输入的k值超出链表长度\n");
    } else {
        printf("倒数第%d个结点的值为%d\n", k, node->val);
    }
    return 0;
}

输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针

思路：

定义两个指针，第一个指针先走 k-1 步，然后第二个指针和第一个指针同时向后移动，直到第一个指针到达链表尾部，此时第二个指针指向的即为倒数第 k 个节点。

代码实现：

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null || k <= 0) {
        return null;
    }
    ListNode first = head;
    for (int i = 0; i < k - 1; i++) {
        if (first.next != null) {
            first = first.next;
        } else {
            return null;
        }
    }
    ListNode second = head;
    while (first.next != null) {
        first = first.next;
        second = second.next;
    }
    return second;
}