Let me explain why it is one pass


  • -1
    Y

    You need two points; the first point goes first for n-1 step from the head, then move the second and first points at the same time; when the first point reaches the end of the list, the second point just reach to the nth nodes which needed to be remove;

    It's easy to tell that the first point move from the head to the tail and then it's done. No matter how much points you use, it's still one pass; no need to reiterate over the list at the second time. And Enjoy it :)

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = head;
        ListNode q = head;
        ListNode pre = null;
        while(n > 1){
            q = q.next;
            n--;
        }
        while(q.next != null){
            q = q.next;
            pre = p;
            p = p.next;
        }
        if(p == head) head = head.next;
        else{
            pre.next = p.next;
        }
        return head;
        
    }

Log in to reply
 

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