Difficulty: Medium, Asked-in: Amazon
Key takeaway: An excellent problem for beginners to learn problem-solving with linked lists. This blog will guide you to work efficiently with linked lists and deal with pointers.
Write a program to remove the Nth node from the end of the linked list, i.e., when the node is traversed from the end, delete the Nth node from there.
Input: 1->2->3->4->5, N = 2, Output: 1->2->3->5
Input: 7->8->4->5->3, N = 1, Output: 7->8->4->5
If M is the length of the linked list, then the Nth node from the end is the (M - N + 1)th node from the beginning. So we can modify the problem to remove the (M − N + 1)th node from the beginning of the list.
struct ListNode
{
int val;
ListNode* next;
ListNode(int data)
{
val = data;
next = NULL;
}
};
ListNode* removeNthNodeListEnd(ListNode* head, int N)
{
if (head == NULL)
return NULL;
int length = 0;
ListNode* temp = head;
while (temp != NULL)
{
length = length + 1;
temp = temp->next;
}
length = length - N;
if (length == 0)
{
temp = head->next;
head->next = NULL;
delete(head);
return temp;
}
ListNode* curr = head;
ListNode* prev = NULL;
while (length > 0)
{
prev = curr;
curr = curr->next;
length = length - 1;
}
prev->next = curr->next;
curr->next = NULL;
delete(curr);
return head;
}
class ListNode:
def __init__(self, data):
self.val = data
self.next = None
def removeNthNodeListEnd(head, N):
if head is None:
return None
length = 0
temp = head
while temp is not None:
length = length + 1
temp = temp.next
length = length - N
if length == 0:
temp = head.next
head.next = None
del head
return temp
curr = head
prev = None
while length > 0:
prev = curr
curr = curr.next
length = length - 1
prev.next = curr.next
curr.next = None
del curr
return head
class ListNode
{
int val;
ListNode next;
ListNode(int val)
{
this.val = val;
this.next = null;
}
}
class Solution
{
public ListNode removeNthNodeListEnd(ListNode head, int N)
{
if (head == null)
return null;
int length = 0;
ListNode temp = head;
while (temp != null)
{
length = length + 1;
temp = temp.next;
}
length = length - N;
if (length == 0)
{
temp = head.next;
head.next = null;
head = null;
return temp;
}
ListNode curr = head;
ListNode prev = null;
while (length > 0)
{
prev = curr;
curr = curr.next;
length = length - 1;
}
prev.next = curr.next;
curr.next = null;
curr = null;
return head;
}
}
We are performing two traversals of the linked list: first, to calculate the length M of the list, and second, to find the (M − N)th node. There are 2M − N operations, so the time complexity in the worst case is O(M). Space complexity is O(1), as we are using constant space here.
The idea here is to use two pointers to find the (N + 1)th node from the end. In the beginning, the first pointer is at the (N + 1)th node from the start, and the second pointer is at the head of the linked list. By moving both pointers one step at a time until the first pointer reaches the end, the second pointer will point to the (N + 1)th node from the end, and we can easily remove the next node, which is the Nth node from the list end.
struct ListNode
{
int val;
ListNode* next;
ListNode(int data)
{
val = data;
next = NULL;
}
};
ListNode* removeNthNodeListEnd(ListNode* head, int N)
{
if (head == NULL)
return NULL;
ListNode* firstPointer = head;
ListNode* secondPointer = head;
for (int i = 1; i <= N; i = i + 1)
firstPointer = firstPointer->next;
if (firstPointer == NULL)
{
ListNode* temp = head->next;
head->next = NULL;
delete(head);
return temp;
}
while (firstPointer->next)
{
firstPointer = firstPointer->next;
secondPointer = secondPointer->next;
}
ListNode* temp = secondPointer->next;
secondPointer->next = temp->next;
delete(temp);
return head;
}
class ListNode:
def __init__(self, data):
self.val = data
self.next = None
def removeNthNodeListEnd(head, N):
if head is None:
return None
firstPointer = head
secondPointer = head
for i in range(1, N + 1):
firstPointer = firstPointer.next
if firstPointer is None:
temp = head.next
head.next = None
del head
return temp
while firstPointer.next:
firstPointer = firstPointer.next
secondPointer = secondPointer.next
temp = secondPointer.next
secondPointer.next = temp.next
del temp
return head
class ListNode
{
int val;
ListNode next;
ListNode(int val)
{
this.val = val;
this.next = null;
}
}
class Solution
{
public ListNode removeNthNodeListEnd(ListNode head, int N)
{
if (head == null)
return null;
ListNode firstPointer = head;
ListNode secondPointer = head;
for (int i = 1; i <= N; i = i + 1)
firstPointer = firstPointer.next;
if (firstPointer == null)
{
ListNode temp = head.next;
head.next = null;
head = null;
return temp;
}
while (firstPointer.next != null)
{
firstPointer = firstPointer.next;
secondPointer = secondPointer.next;
}
ListNode temp = secondPointer.next;
secondPointer.next = temp.next;
temp = null;
return head;
}
}
If the length of the linked list is M, then the firstPointer will move M steps, and the secondPointer will move M - N steps. So, pointer movement = 2M - N, and time complexity = O(M). Space complexity = O(1) as we are using constant space.
If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.