There is NO such solution with ONE pass!


  • 3
    A

    Many people think a fast-slow pointer solution is one-pass. Actually, it is not. It is more than one pass and less than two.

    This is the same as if the list is iterated once to count the number of nodes, and then traversed from the beginning again for the count of slow-pointer.


  • -6
    U

    Not really. In two pointer solution, the iteration takes only 1 pass. This greatly differs from 1.x pass you mentioned.


  • 0
    E

    Here's my one pass solution.

    public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        List<ListNode> list = new LinkedList<>();
        ListNode temp = head;
        while(temp!=null){
            list.add(temp);
            temp = temp.next;
        }
        int size=list.size();
        if(n==1){
            if(size<=1) return null;
            else list.get(size-n-1).next=null;
        } 
        else if(n==size) head = list.get(1);
        else list.get(size-n-1).next = list.get(size-n+1);
        return head;
    }
    

    }


  • 1
    P

    Coping all ListNode nodes into List<ListNode> and then doing list.get(size-n+1) and claiming it's one pass is ridiculous.


  • 2
    P

    Agree with Alpher.
    Two pointer solution is not one pass solution.
    Perhaps there is a confusion between one_pass and O(n) complexities.

    Is two pointers an O(n) solution? Yes. Is it one_pass solution? Obviously not.

    Moving two pointers, first one Length times and another one Len - n times is not different from get-length-of-the-list-first solution.
    Basically they are the same: L (list Length) iterations to get length of the list and then Len - n iterations to get to the node which needs to be removed.
    When n == 1 it's almost two passes, not one but still O(n).


  • 1
    A

    @Alpher You are actually right. There is no real ONE pass solution with O(1) space complexity.
    Two pointers solution is no different than combining the two loops. It doesn't save cycles, but only nice to the eyes.
    For the other recursive solution, it is no different than saving all addresses in a vector in heap. In fact all addresses are saved in stack instead. If you pause at the most inner recursion and inspect stack, you will find all addresses of the linked list there.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.