查找链表倒数第k个结点

可以使用双指针法来查找链表倒数第k个节点。具体来说，我们可以定义两个指针p1和p2，初始时它们都指向链表的头结点。然后，我们先将p2向后移动k个结点，接着同时移动p1和p2，直到p2指向链表的尾结点。此时，p1所指向的结点就是链表倒数第k个结点。

需要注意的是，如果链表的长度少于k，那么我们无法找到倒数第k个结点，这时需要根据题目要求返回空指针或抛出异常。

以下是示例代码实现：

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

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

时间复杂度为$O(n)$，其中n是链表的长度。空间复杂度为$O(1)$。

相关问题

第9关：查找链表倒数第k个结点

题目描述：给定一个链表，输出该链表倒数第k个节点，如果k大于链表长度则返回空。

算法思路：使用双指针，先让第一个指针移动k-1个节点，然后再让第一个指针和第二个指针同时移动，当第一个指针到达链表结尾时，第二个指针指向的就是倒数第k个节点。

参考代码实现（Python）：

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

def findKthToTail(head, k):
    if head is None or k <= 0:
        return None
    
    # 定义两个指针，初始都指向头结点
    p1 = p2 = head
    
    # 让第一个指针移动k-1个节点
    for i in range(k-1):
        if p1.next is None:
            return None
        p1 = p1.next
    
    # 两个指针同时移动，直到第一个指针到达链表结尾
    while p1.next is not None:
        p1 = p1.next
        p2 = p2.next
    
    return p2

参考代码实现（Java）：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public ListNode findKthToTail(ListNode head, int k) {
    if (head == null || k <= 0) {
        return null;
    }
    
    // 定义两个指针，初始都指向头结点
    ListNode p1 = head;
    ListNode p2 = head;
    
    // 让第一个指针移动k-1个节点
    for (int i = 0; i < k-1; i++) {
        if (p1.next == null) {
            return null;
        }
        p1 = p1.next;
    }
    
    // 两个指针同时移动，直到第一个指针到达链表结尾
    while (p1.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    
    return p2;
}

查找链表倒数第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