I've been going through algorithm challenges on LeetCode and just completed "Remove Nth Node From End of List".

Many of the top answers claimed to have found a "one pass" solution and I've included a Java example below.

Please could someone explain why "while(n-->0) h2=h2.next;" doesn't count as an extra pass of the linked list and, therefore, make this a "two pass" solution?

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

I've looked in the comments to this and other solutions and couldn't find an answer. Equally, a general Google search didn't yield an explanation.

Thanks in advance.

CodePudding user response：

No, it's not one-pass. One-pass is defined with respect to a sequential I/O mechanism (canonically a tape) and means that each piece of data is read at most once, in order. Analogizing the linked list to the tape here, this algorithm is not one-pass because in general, some node will have its next field read once by h2=h2.next (in either loop) and again by h1=h1.next in the second loop.

CodePudding user response：

The algorithm is not single pass, but not because of the first loop.

The first loop performs a partial pass on n elements.

The second loop performs two simultaneous partial passes on l-n elements (that on h2 being complementary to that in the first loop). In total, 2l-n lookups of next fields.

A single-pass solution can be implemented with the help of a FIFO queue of length n, but this is "hiding" a partial pass.