查找链表倒数第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 个节点，可以使用双指针的方法。首先定义两个指针，一个指针称为 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)