如何高效地一次性找到单向链表从末尾算起的第 k 个节点和从开头算起的第 m 个节点？

Question

我正在使用Java中的单链表，需要实现一种方法，可以在一次遍历中同时找到从列表末尾开始的第k个节点和从列表开头开始的第m个节点。该解决方案应该是高效的，并且除了几个变量之外不需要额外的空间。

具体要求如下：

实现一种方法，可以一次性找到链表中从尾数第k个节点和从头开始第m个节点。 如果列表没有足够的节点（即，如果 k 或 m 超过列表的长度），请妥善处理（例如，返回 null 或默认值）。 例如，给定链表 1 -> 2 -> 3 -> 4 -> 5 且 k = 2 且 m = 3，该方法应从末尾返回节点 3 (4)，从开头返回节点 3 (3) .

这是我的链表实现的简化版本：

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

public class FindNodes {

public static ListNode[] findNodes(ListNode head, int k, int m) {
    // Implement the logic here
}

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].val);
        System.out.println("M-th node from the beginning: " + result[1].val);
    } else {
        System.out.println("Nodes not found.");
    }
}

}

如何实现findNodes方法，高效一次性找到链表尾部第k个节点和链表头第m个节点？任何详细的解释或代码示例将不胜感激！

Answer 1

说明：

使用两个指针查找单向链表中从末尾算起的第 (k) 个节点和从开头算起的第 (m) 个节点：

1. 初始化两个指针：将两个指针从列表的头部开始。
2. 向前移动第一个指针 ( k ) 步：向前移动第一个指针 ( k ) 步。
3. 移动两个指针直到第一个指针到达末尾：每次移动两个指针一步，直到第一个指针到达末尾。然后第二个指针将位于从末尾开始的第 (k) 个节点。
4. 找到从头开始的第（m）个节点：从头开始向前移动第三个指针（m）步，到达从头开始的第（m）个节点。
5. Return the Nodes：返回第二个和第三个指针指向的节点。

时间复杂度：O(n)，其中n是列表中的节点数，因为列表仅遍历一次。

public static ListNode[] findNodes(ListNode head, int k, int m) {
    // Implement the logic here
    // Assuming both m and k to be less than or equal to the length of the linked list
    ListNode temp1 = head, temp2 = head, temp3 = head;
    ListNode[] ans = new ListNode[2];

    int i = 0, j = 0;
    while(i<k){
        temp1 = temp1.next;
        i++;
    }
    while(j<m){
        temp3 = temp3.next;
        j++;
    }
    ans[1] = temp3;
    while(temp1 != null){
        temp2 = temp2.next;
        temp1 = temp1.next;
    }
    ans[0] = temp2;
    return head;
}