链表的部分遍历算作链表的 "one pass" 吗？

Question

我一直在完成 LeetCode 上的算法挑战，刚刚完成“从列表末尾删除第 N 个节点”。

许多热门答案声称找到了“一次通过”的解决方案，我在下面包含了一个 Java 示例。

请有人解释为什么“while(n-->0) h2=h2.next;”不算作链表的额外传递，因此，使其成为“两次传递”解决方案？

public ListNode RemoveNthFromEnd(ListNode head, int n)  {
    ListNode h1=head, h2=head;

    while(n-->0) h2=h2.next;

    if(h2==null)return head.next;  // The head need to be removed, do it.

    h2=h2.next;
    
    while(h2!=null){
        h1=h1.next;
        h2=h2.next;
    }
    h1.next=h1.next.next;   // the one after the h1 need to be removed
    return head;
}

我查看了对此解决方案和其他解决方案的评论，但找不到答案。同样，一般 Google 搜索也没有给出解释。

提前致谢。

Answer 1

不，这不是一次通过。一次通过是相对于顺序 I/O 机制（通常是磁带）定义的，意味着每条数据最多按顺序读取一次。在这里将链表类比为磁带，这个算法不是一次性的，因为一般来说，一些节点的 next 字段将被 h2=h2.next 读取一次（在任一循环中）并再次被 h1=h1.next 在第二个循环中。

Answer 2

算法不是single pass，但不是因为第一次循环。

第一个循环对 n 个元素执行部分传递。

第二个循环对 l-n 元素执行两次同时部分传递（h2 上的元素与第一个循环中的元素互补）。总共 2l-n 次查找 next 字段。

单通道解决方案可以借助长度为 n 的 FIFO 队列来实现，但这是“隐藏”了部分通道。

链表的部分遍历算作链表的 "one pass" 吗？

Does a partial traversal of a linked-list count as "one pass" of the list?

java

algorithm

loops

linked-list