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.


  1. The number of nodes in the list is sz.
  2. \(1 \leq sz \leq 30\).
  3. \(0 \leq Node.val \leq 100\).
  4. \(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
   1. if ~fast_pos - slow_pos < n~
      1. ~fast_node =, ~fast_pos += 1~
   2. if ~fast_pos - slow_pos == n~
      1. ~fast_node =, ~fast_pos += 1~
      1. ~slow_node =, ~slow_pos += 1~

2.3. Code

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_pos += 1

    # critical part
    if fast_node is None:

        fast_node =
        slow_node = =

    return head

2.3.1. Complexity Time complexity:

O(N) Space complexity:


2.4. Leetcode solution

<<imports for typing>>

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.

4. Log time