python查找链表中倒数第k个结点

在Python中，查找链表中倒数第k个节点通常需要先遍历链表获取链表的长度，然后从头开始再次遍历链表，这次是在找到第k个节点之后再前进一步，指向的就是倒数第k个节点。这是一个典型的双指针问题，可以使用两个指针p1和p2，初始时p2位于p1之前k步。

以下是实现该功能的一个简单示例：

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

def find_kth_to_last(head, k):
    p1 = p2 = head

    # 首先移动p2 k步
    for _ in range(k):
        if not p2:
            return None  # 如果k大于链表长度，则返回None
        p2 = p2.next

    # 然后同时移动p1和p2直到p2到达末尾
    while p2.next:
        p1 = p1.next
        p2 = p2.next

    return p1  # 返回倒数第k个节点

在这个函数中，如果`find_kth_to_last`成功找到了倒数第k个节点，它将返回那个节点；如果没有找到（比如k大于链表长度），则返回`None`。

相关问题

查找链表中倒数第k个结点

要查找链表中倒数第 k 个节点，可以使用双指针的方法。首先定义两个指针，一个指针称为 slow，一个指针称为 fast。将 fast 指针先向前移动 k-1 步，然后 slow 指针从头开始与 fast 指针同时向后移动，直到 fast 指针到达链表末尾。
这时，slow 指针所指的节点就是倒数第 k 个节点。
下面是示例代码实现：

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

def find_kth_from_end(head, k):
    slow = fast = head
    for _ in range(k):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    return slow

# 创建链表
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 测试查找倒数第 k 个节点
k = 2
result = find_kth_from_end(head, k)
print("倒数第", k, "个节点的值为:", result.val)

输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第一个结点

### 回答1：
可以使用双指针法来解决这个问题。首先定义两个指针p1和p2，让它们都指向链表的头结点。然后让p1向前移动k-1个结点，此时p1和p2之间的距离为k-1。接着让p1和p2同时向前移动，直到p1指向链表的最后一个结点。此时p2所指向的结点就是倒数第k个结点。

具体实现可以参考以下代码：

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

def findKthToTail(head, k):
    if not head or k <= 0:
        return None
    p1 = p2 = head
    for i in range(k-1):
        if p1.next:
            p1 = p1.next
        else:
            return None
    while p1.next:
        p1 = p1.next
        p2 = p2.next
    return p2

其中，head表示链表的头结点，k表示要查找的倒数第k个结点。如果链表为空或k小于等于0，直接返回None。否则，定义两个指针p1和p2，让它们都指向头结点。然后让p1向前移动k-1个结点，此时p1和p2之间的距离为k-1。接着让p1和p2同时向前移动，直到p1指向链表的最后一个结点。最后返回p2所指向的结点即可。

### 回答2：
题目描述

输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第一个结点。

思路分析

题目让我们找到倒数第k个结点。对于单向链表，无法直接从后往前遍历，所以我们只能从前往后遍历链表，同时记录访问过的节点数，当访问第k个结点时，再开始访问下一个节点，直到遍历到链表末尾为止。

一般我们采用双指针，设两个指针p,q，p先走k步，然后p和q同时往前，当p走到链表末尾时，q所指向的结点就是倒数第k个结点。

总结思路：

1.定义两个指针p，q；

2.p先走k步；

3.q从头开始，当p到达尾结点时，q所在位置就是倒数第k个结点。

代码实现

首先，我们定义两个指针p，q，p先走k步：

样例输入：

链表：1->2->3->4->5

输出：

倒数第2个结点：4

### 回答3：
这道题考察的是单向链表的基本操作和指针的运用。我们可以采用双指针的方法来解决该问题。

具体方法如下：

1.定义两个指针p和q，初始时，p和q都指向链表的头结点。

2.让其中一个指针q先走k-1步，然后p和q一起往后移动，直到q指向链表的最后一个节点。

3.此时p指向的结点就是倒数第k个结点。

代码实现如下：

struct ListNode{
int val;
ListNode* next;
ListNode(int x):val(x), next(nullptr){}
};

ListNode* findKthToTail(ListNode* head, int k){
if(head == nullptr || k == 0){
return nullptr;
}
ListNode* p = head;
ListNode* q = head;
for(int i=0; i<k-1; i++){
if(q->next != nullptr){
q = q->next;
}
else{
return nullptr;
}
}
while(q->next != nullptr){
p = p->next;
q = q->next;
}
return p;
}

以上代码中，startTime 和 endTime 分别表示起始时间和结束时间，dt 则表示时间差。如果起始时间为空，则将 startTime 赋值为当前时间，否则计算时间差并输出。

完整代码如下：