# The Blind 75 Leetcode Series: Remove Nth Node From End of List

Today, we are working on Remove Nth Node From End of List.

Given the

`head`

of a linked list, remove the`nth`

node from the end of the list and return its head.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:The number of nodes in the list is

`sz`

.

`1 <= sz <= 30`

`0 <= Node.val <= 100`

`1 <= n <= sz`

Follow up:Could you do this in one pass?

The problem gives pretty clear instruction already. I think these constraints are well enough for us to work on, so let’s dive into it directly.

I was thinking what would be the most direct, brute-force approach. Normally, it would be a way to check “all the combinations”, but what would it be in this case?

Maybe instead we can check for all conditions and make sure the solution satisfies.

When a `n`

is given, we can assume 3 things:

- n-th node represents the beginning of the list (n=len(link_list))
- n-th node represents the end of the list (n=1)
- n-th node represents a node somewhere in the middle (1 < n < len(link_list))

Since we are checking n-th node **from the end of the list**, we can go through the entire list once, store all nodes, and check these 3 conditions accordingly.

`def removeNthFromEnd(head, n):`

nodes = []

begin = ListNode()

begin.next = head

while head:

nodes.append(head)

head = head.next

# head, n = len(nodes)

if n == len(nodes):

begin.next = begin.next.next

# tail, n = 1

elif n == 1:

nodes[-2].next = None

# mid, len(nodes) > n > 1

else:

nodes[len(nodes) - n - 1].next = nodes[len(nodes) - n + 1]

return begin.next

We start with initializing the the list to store all the nodes, a `begin`

that points to the `head`

as its `next`

node, and then iterating through the entire linked list to get all the nodes and stored in the list.

Then we check for the 3 conditions.

First, if the n-th node from behind represents the beginning of the list, then we simply need to point our `begin.next`

to the node after the head, which is `begin.next.next`

. This is safe to do because even if `head.next`

does not exist, `begin.next.next`

will effectively point to the right null node (or `None`

).

Second, if the n-th node from behind represents the end of the list, then we can eliminate the last node and point second the last node to a null node, thus, `nodes[-2].next = None`

Last, for any of the node in the middle, we just point the previous node’s `next`

to the node after, effectively skipping the target node.

So what’s the time complexity? We only iterate through the list once and retrieving the element through index is constant, so we just have O(n)

`def removeNthFromEnd(head, n):`

nodes = []

begin = ListNode()

begin.next = head

while head: # O(n)

nodes.append(head)

head = head.next

if n == len(nodes):

begin.next = begin.next.next

elif n == 1:

nodes[-2].next = None

else:

nodes[len(nodes) - n - 1].next = nodes[len(nodes) - n + 1] # O(1) for get item

return begin.next

What can be another solution? What if we have 2 pointers, one is `n`

steps ahead of the other? Then we move both nodes toward the end of the list. When the node ahead reaches the end, the node behind will be at exactly `n-1 steps from the end of the list`

, then we just need to point that node’s `next`

to the node’s `next.next`

, skipping the next node, and we are done.

Let’s take a look of the example given at the beginning another time for some visual aid

To put this in code:

def removeNthFromEnd(head, n):

ahead = behind = head

for _ in range(n): # put ahead pointer to position

ahead = ahead.next

if not ahead: # linked list shorter than n, simply return head.next

return head.next

while ahead.next: # check if ahead has reached to the end, if not move both pointers forwards

ahead = ahead.next

behind = behind.next behind.next = behind.next.next # skip the target node as now the behind node reaches 1 step before the target node

return head

What’s the time complexity with this approach? We still only loop through the linked list once, so it’s still O(n)

def removeNthFromEnd(head, n):

ahead = behind = head

for _ in range(n): # O(1), constant to "n"

ahead = ahead.next

if not ahead: # O(1)

return head.next

while ahead.next: # O(n)

ahead = ahead.next

behind = behind.next behind.next = behind.next.next # O(1)

return head

This approach is definitely cleaner as we don’t have to check each possible scenario, but it’s not necessarily faster. On average, the first approach reaches ~ 30ms run time which the second approach reaches ~55ms run time. Keep in mind that when you are whiteboarding, the run time is usually not shown, which means interviewers will usually look for a cleaner solution if the time complexity for all answers are the same. If you insist that your solution runs faster, you need to explain to the interviewers why it runs faster. We usually speak about time complexity using the worst case scenario, so maybe you can prove why your solution hits the worst case way less often than the other, cleaner approach. If you don’t think you can convince the interviewers, I’d stick with the cleaner solution. Remember, you only have ~ 45 mins and you want to make things as concise as possible.

There you have it! Another problem down!

*Buy my a coffee: **https://www.buymeacoffee.com/jonathanckz*