Remove Nth Node From End of List — Day 107(Python)

Today we will be working on the LinkedList problem. Let’s look into the problem statement.

19. 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?

One way to solve this problem is to find at what position we want to remove the node from. To identify that position, first, find the length of the linked list, then subtract N from the length of the linked list.

After finding the position, we will traverse through the linked list and then delete the node in that position. We will use 3 variables that point to the previous node, current node, and next node. Once the current node reaches the required position, we will point the previous node to the next node, thus removing the current node.

Let us look into the code.

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def length_ll(self, head):
length_of_linkedlist = 0
while(head):
length_of_linkedlist += 1
head = head.next
return length_of_linkedlist

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length_of_linkedlist = self.length_ll(head)
prev, curr = None, head
position_to_remove = length_of_linkedlist - n
if(length_of_linkedlist == 1 and n == 1 or position_to_remove == 0):
return head.next
while(curr):
nex = curr.next
if(position_to_remove == 0):
prev.next = nex
break
else:
prev = curr
curr = nex
position_to_remove -= 1
return head

Complexity Analysis

Time Complexity

We are traversing through the linked list twice; once to find the length of the linked list and second to remove the node. The time complexity is O(N) where N is the length of the Linked list.

Space Complexity

We are not using any extra space and hence space complexity is O(1).

How can we solve this problem in one pass? I had to look into the solution to understand that having two-pointers are considered as one pass.

Pointer 1 will move until we reach n. Once pointer 1 reaches n, we will start pointer 2 until pointer 1 reaches the end of the linked list. The node which pointer 2 points at, is the node that needs to be removed.

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if head.next is None:
return None
fast,slow=head,head
for i in range(n):
fast=fast.next
if not fast:
return head.next
while fast.next:
slow=slow.next
fast=fast.next
if n==1:
slow.next=None
else:
slow.next=slow.next.next
return head

Complexity Analysis

Time Complexity

We are traversing through the linked list using two pointers, hence time complexity is O(N).

Space Complexity

We are not using any extra space and hence space complexity is O(1).

--

--

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