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

查找链表倒数第n个结点

查找链表倒数第n个节点是一种常见的链表操作，可以使用双指针法来解决。这种方法涉及两个指针，通常称为快指针（fast）和慢指针（slow）。以下是步骤：

1. **初始化**：
- 将快指针设置为链表头节点，快指针先走两步；
- 将慢指针设置为链表头节点，只走一步。

2. **移动指针**：
- 当快指针到达链表尾部（即空节点或下一个节点为空）时，慢指针会停在倒数第二个节点上；
- 因为快指针每次走两步，所以当它到达尾部时，慢指针恰好走了n步。

3. **找到倒数第n个节点**：
- 返回慢指针指向的节点，这就是我们要找的倒数第n个节点。

如果你需要实现这个算法，这是一个伪代码示例：

def find_kth_to_last(head, n):
    fast = head
    slow = head
    for _ in range(n):
        if fast is not None:
            fast = fast.next
        else:
            return None  # 如果链表长度小于n，返回None

    while fast is not None:
        fast = fast.next
        slow = slow.next

    return slow