查找链表倒数第k结点

查找链表倒数第K个节点是一个常见的数据结构和算法问题。给定一个单向链表和一个整数K，你需要找到链表中倒数第K个节点。这个问题可以使用双指针法来解决，具体步骤如下：

1. 创建两个指针，初始时都指向链表的头节点，分别命名为`p1`和`p2`，并将`p2`向前移动K步。

2. `p1`开始正常遍历链表，每次`p1`前进一步，`p2`保持不变。

3. 当`p1`到达链表尾部时，`p2`正好停在倒数第K个节点处，因为`p2`已经比`p1`多走了K步。

4. 如果K等于0，则直接返回头节点，因为链表本身就是一个倒序的链表。

以下是Python伪代码的一个简单版本：

def find_kth_to_last(head, k):
    p1 = p2 = head
    for _ in range(k):
        if not p2:
            return None  # 如果k大于链表长度，返回None
        p2 = p2.next
    while p2:
        p1 = p1.next
        p2 = p2.next
    return p1

相关问题

查找链表倒数第k结点完整C代码

查找链表倒数第K个节点是一个常见的链表操作问题。这里提供一个简单的C语言解决方案，使用两个指针法：

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

// 定义链表结构体
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 查找链表倒数第K个节点
ListNode* findKthToTail(ListNode* head, int k) {
    if (head == NULL || k <= 0) {
        return NULL;
    }

    ListNode* slow = head;
    ListNode* fast = head;
    for (int i = 0; i < k - 1; i++) {
        if (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
        } else {
            return NULL; // 如果快指针到达了链表尾部，说明链表长度小于k
        }
    }

    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建测试链表：1->2->3->4->5
    ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    int k = 2; // 我们要找的是倒数第二个节点
    ListNode* result = findKthToTail(head, k);
    if (result != NULL) {
        printf("The node at position %d is %d\n", k, result->val);
    } else {
        printf("Invalid value of k or empty list.\n");
    }

    free(head); // 释放内存
    return 0;
}

这个程序首先创建一个链表，然后调用`findKthToTail`函数找到指定位置的节点。如果链表长度小于k，它会返回NULL。运行此代码，你可以看到倒数第k个节点的值。

查找链表倒数第k个结点

查找链表倒数第k个结点可以使用双指针法。首先定义两个指针p1和p2，都指向链表的头结点。然后将p1指针向前移动k个结点，此时p1和p2之间的距离为k。接着同时移动p1和p2指针，直到p1指向链表的末尾，此时p2指向的结点即为倒数第k个结点。

具体实现代码如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def find_kth_to_tail(head: ListNode, k: int) -> ListNode:
    if not head or k <= 0:
        return None

    p1 = p2 = head
    for i in range(k-1):
        if not p1.next:
            return None
        p1 = p1.next

    while p1.next:
        p1 = p1.next
        p2 = p2.next

    return p2

其中，head为链表的头结点，k为倒数第k个结点的位置，函数返回倒数第k个结点。如果链表为空或k小于等于0，返回None。