Java solution, 1 ms, one pass


  • 0
    J
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // use a dummy node to track the head; in case head is the one to be removed
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode left = dummy, right = dummy;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }

  • 0
    F

    For the case of large length (lets call it L) of the list, and small n, you actually traverse n + L-n + L-n nodes which in 2L -n , and for small n, it is actually 2 passes of the list ( one for left and one for right variables)


Log in to reply
 

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