如何在一次遍历中高效查找单链表的倒数第k个和正数第m个节点？

核心实现思路 #

要在一次遍历中完成两个节点的查找，结合双指针法（定位倒数第k个节点）和计数遍历（定位正数第m个节点）即可高效实现：

1. 先用快指针提前走k步，同步计数并记录正数第m个节点；
2. 快慢指针同步向前移动，直到快指针抵达链表末尾，此时慢指针指向的就是倒数第k个节点；
3. 遍历全程统计链表总长度，用于最终判断k、m是否超出链表范围。

完整代码实现 #

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

public class FindNodes {

    public static ListNode[] findNodes(ListNode head, int k, int m) {
        ListNode[] result = new ListNode[2];
        // 处理非法输入：k或m为非正整数直接返回
        if (k <= 0 || m <= 0) {
            return result;
        }

        ListNode fast = head;
        ListNode slow = head;
        ListNode mNode = null;
        int stepCount = 0;
        int listLength = 0;

        // 阶段1：快指针先走k步，同步找正数第m个节点、统计链表长度
        while (fast != null && stepCount < k) {
            listLength++;
            stepCount++;
            if (stepCount == m) {
                mNode = fast;
            }
            fast = fast.next;
        }

        // 如果快指针未走完k步就到末尾，说明k超过链表长度
        if (stepCount < k) {
            result[1] = mNode;
        } else {
            // 阶段2：快慢指针同步移动，直到快指针到末尾，继续统计长度、补找m节点
            while (fast != null) {
                listLength++;
                stepCount++;
                if (stepCount == m) {
                    mNode = slow.next;
                }
                fast = fast.next;
                slow = slow.next;
            }
            // 此时慢指针就是倒数第k个节点
            result[0] = slow;
        }

        // 最终校验m是否超出链表长度
        if (m > listLength) {
            result[1] = null;
        } else {
            result[1] = mNode;
        }

        // 若两个节点都不存在，返回null；否则返回结果数组
        return (result[0] == null && result[1] == null) ? null : result;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        int k = 2;
        int m = 3;
        ListNode[] result = findNodes(head, k, m);

        if (result != null && result.length == 2) {
            System.out.println("K-th node from the end: " + (result[0] != null ? result[0].val : "null"));
            System.out.println("M-th node from the beginning: " + (result[1] != null ? result[1].val : "null"));
        } else {
            System.out.println("Nodes not found.");
        }
    }
}

详细步骤解释 #

1. 非法输入拦截：k或m为非正整数时，直接返回含null的结果数组，因为不存在第0个或负数位置的节点。
2. 快指针前置移动：快指针先向前移动k步，每移动一步同步计数：
   • 当计数等于m时，记录当前快指针指向的节点，即为正数第m个节点；
   • 累计链表长度，用于后续判断k、m是否越界。
3. k合法性校验：若快指针移动不足k步就到达链表末尾，说明k大于链表长度，倒数第k个节点置为null。
4. 快慢指针同步遍历：若k合法，快慢指针同步向前移动至快指针抵达末尾：
   • 继续统计链表长度，若m大于k，在计数到达m时补记正数第m个节点；
   • 快指针走完链表时，慢指针因滞后k步，正好指向倒数第k个节点。
5. m合法性校验：最后判断m是否超过链表总长度，若是则将正数第m个节点置为null。
6. 结果返回：若两个节点都不存在则返回null，否则返回包含目标节点的数组。

边界场景验证 #

• 空链表：返回null；
• k=0/m=0：返回含null的数组；
• k>链表长度：倒数第k个节点为null，正数第m个节点合法则返回；
• m>链表长度：正数第m个节点为null，倒数第k个节点合法则返回；
• k=m：如链表1->2->3->4->5，k=3、m=3时，两个节点均为3。

内容的提问来源于stack exchange，提问作者Ashini Ayodhya