Remove Nth Node From End of List

Note this one

1. Description

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

Constraints:

The number of nodes in the list is sz.
\(1 \leq sz \leq 30\).
\(0 \leq Node.val \leq 100\).
\(1 \leq n \leq sz\).

1.1. Examples:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Input: head = [1], n = 1
Output: []

Input: head = [1,2], n = 1
Output: [1]

2. Solution

2.1. Understanding the problem

From the provided code we can see it's a singly linked list.

We can use fast_node and fast_pos that will reach the end of the list, and slow_node and slow_pos that will be n node(s) away from fast_node. Slow node will be tracking the previous node of the node to be removed.

Given that the trivial case [1] and n=1 returns [], we have slow_node = head, slow_pos = 0 and fast_node = head and fast_pos = 0.

In the end we want to first have fast_node and slow_node to be n nodes away and then move both of them to the next node, until fast_node reaches the end of the list.

Note that slow_node will be the node that is connected to fast_node, and the node between them will be removed.

2.2. Algorithm

Incorrect algorithm where I put progression of space between slow_node and fast_node by moving fast_node, and slow_node and fast_node moving together, under the same while loop. In this case I had difficulty handling the edge case with head being the element to be removed via checking if fast_node is None. I had no way of returning from the while loop. Once the while loop finishes, I have no way of distinguishing the following situations so I won't know if I need to remove the head:

n = 3

1	2	3	None
s		f

n = 3

1	2	3	4	None
	s		f

1. Initialise ~fast_node = head~, ~fast_pos = 0~, ~slow_node = head~, ~slow_pos = 0~
2. while ~fast_node.next~
   1. if ~fast_pos - slow_pos < n~
      1. ~fast_node = fast_node.next~, ~fast_pos += 1~
   2. if ~fast_pos - slow_pos == n~
      1. ~fast_node = fast_node.next~, ~fast_pos += 1~
      1. ~slow_node = slow_node.next~, ~slow_pos += 1~

2.3. Code

Listing 1: 19 Remove Nth Node from end of list my solution

def removeNthFromEnd(self, head, n):
    """
    :type head: ListNode
    :type n: int
    :rtype: ListNode
    """

    fast_node = head
    fast_pos = 0
    slow_node = head
    slow_pos = 0

    while fast_pos - slow_pos < n:
        fast_node = fast_node.next
        fast_pos += 1

    # critical part
    if fast_node is None:
        return head.next

    while fast_node.next:
        fast_node = fast_node.next
        slow_node = slow_node.next

    slow_node.next = slow_node.next.next

    return head

Listing 2: 19 Remove Nth Node from end of list my solution-results

2.3.1. Complexity

2.3.1.1. Time complexity:

O(N)

2.3.1.2. Space complexity:

O(1)

2.4. Leetcode solution

Listing 3: 19 Remove Nth Node from end of list leetcode solution

<<imports for typing>>

Listing 4: 19 Remove Nth Node from end of list leetcode solution-results

2.4.1. Time complexity:

2.4.2. Space complexity:

3. More analysis

3.1. General thoughts

I had to check Leetcode solution for this one as my original wasn't right.

I think the hardest part is again the edge cases, especially how to handle a linked list of only one element, although it's not really relevant in this case, and how to remove the head node.

19. Remove Nth Node From End of List