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 = 2
Output: [1,2,3,5]

Example 2:

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

Example 3:

Input: head = [1,2], n = 1
Output: [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:

  1. n-th node represents the beginning of the list (n=len(link_list))
  2. n-th node represents the end of the list (n=1)
  3. 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store