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

相关问题

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

第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;
}