Remove Nth Node From End of List LeetCode

Question

I'm doing the Remove Nth Node from End of List LeetCode challenge:

Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Follow up: Could you do this in one pass?

My code is failing on some test cases:

[1,2]
2

And I get this report:

Output [1]
Expected [2]

I've read the solutions already and it appears that my solution is the same as the one written, but I can't figure out where my mistake is. My code is as follows:

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    pointer1 = head
    pointer2 = head
    count = 0
    if not pointer1.next:
        return pointer1.next
    while pointer2 is not None:
        if count > n:
            pointer1 = pointer1.next
        pointer2 = pointer2.next
        count += 1
    pointer1.next = pointer1.next.next
    return head

I've been at this for half an hour now and I can't figure out hwo to fix it. Can someone please help?

Answer 1

Just sharing approaches in Java code snippets (in case anyone is interested for this problem)

Approach #1

Using two iterations - in the first iteration finding the total number of elements in the list to find the index of the element to delete from the beginning of the array and deleting it.

        public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        if (n < 0) {
            return head;
        }
        //find size of the list
        int size = 0;
        ListNode current = head;
        while (current != null) {
            size++;
            current = current.next;
        }
        if (n > size) {
            return head;
        }
        int indexOfTheElementToDelete = size - n;
        ListNode previous = null;
        current = head;
        int currentNodeIndex = 0;
        while (currentNodeIndex < indexOfTheElementToDelete) {
            previous = current;
            current = current.next;
            currentNodeIndex++;
        }
        if (previous != null) {
            if (current != null) {
                previous.next = current.next;
                current.next = null;
            } else {
                // last element to delete
                previous.next = null;
            }
            return head;
        }
        // first element
        ListNode newHead = current.next;
        current.next = null;
        return newHead;
    }

Approach #2

1. It only traverses the list once

2. And to accomplish that the basic idea is to maintain two pointers which are always distanced by n (say slow and fast pointers). And moving both of them such that fast pointer reaches the end - the code snippet below has details.

       public ListNode removeNthFromEnd(ListNode head, int n) {
       if (head == null) {
           return null;
       }
       if (n <= 0) {
           return head;
       }
       ListNode start = new ListNode();
       start.next = head;
       ListNode slow = start;
       ListNode fast = head;
       int indexOfFastNode = 1;
       while (indexOfFastNode < n && fast.next != null) {
           fast = fast.next;
           indexOfFastNode++;
       }
       if (n > indexOfFastNode) {
           return head;
       }
       while (fast.next != null) {
           fast = fast.next;
           slow = slow.next;
       }
       ListNode temp = slow.next;
       slow.next = slow.next.next;
       temp.next = null;
       return start.next;
   }
   

Answer 2

Your solution will fail when n is equal to the number of nodes in the list. In that case you are supposed to remove the first node from the list, and by consequence you should return head.next.

NB: the if you have before the while loop tests for a very specific instance of that case, i.e. when the list has just one element. But as explained above this action should apply in a more generic case than is identified in the if.

So, the following if condition could be dropped:

if not pointer1.next:
    return pointer1.next

And add a condition after the while loop:

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    pointer1 = head
    pointer2 = head
    count = 0
    while pointer2 is not None:
        if count > n:
            pointer1 = pointer1.next
        pointer2 = pointer2.next
        count += 1
    if count > n:
        pointer1.next = pointer1.next.next
        return head  
    else:
        return head.next