Get this book -> Problems on Array: For Interviews and Competitive Programming
In this article, we have explained two approaches to Remove N-th Node from end of Singly Linked List. We can do this in single pass / one traversal in O(N) time.
Table of contents:
- Introduction to Linked List
- Approach 1: Making two passes through Linked List
- Approach 2: Going through the list once, one pass
Prerequisites: Singly Linked List, Slow Fast pointer technique
Similar problems you should learn about:
This is similar to Leetcode Problem 19. Remove Nth Node From End Of List.
Introduction to Linked List
A linked list is a dynamic linear data structure in which elements form a sequence of nodes and each node is linked to another using pointers.
This data structure is known for efficient insertions and deletions from any position, but has costly access times.
There are 4 types of linked lists each having is own uses and applications, these are, singly linked lists, doubly linked lists, circular linked lists and doubly circular linked lists.
You can read more on these on the link provided at the end of this post.
Here we shall cover removing nth node from the end of a singly linked list but first we need to discuss the structure of a singly linked list to gain some insight on how we can perfom the operation.
Singly linked list structure.
The head node which denotes the begining of the list.
A node contains data field and pointer to next node called next.
The last node of a singly linked list next pointer points to null denoting that it is the node marking the end of the list.
Before we start solving this problem we need to understand how deleting a node in a linked list actually works.
Here are the procedures pictorially.
Deleting first node
- Make head pointer point to next node after head.
- Free memory of head node.
Deleting middle nodes
- Traverse to the previous node before the node pending deletion.
- Make next pointer of previous node to point to node after the node to be deleted which exculdes the deleted node.
- Free memory of deleted node.
Deleting last node
- Traverse to the second last node in linked list.
- Make its next pointer point to null denoting end of the list.
- Free memory of deleted node.
Now having that in mind we can delete nth node from end of list.
Solving problem programmatically:
Inputs: pointer to head of linked list, n denoting nth element from end.
Output: pointer to head of linked list without nth element from end.
We can solve it in couple of ways, i shall be discussing two approaches.
Approach 1: Making two passes through Linked List
In the first pass we get the length of the list. Once we have it we can restructure the problem to trying to remove the (length - n + 1)th node from the begining of the list.
In the second pass, we remove the nth node from the end. We do this by linking the next pointer of (length - n)th node to (length - n + 2) node.
Example:
List = [1, 4, 7, 9, 11]
n = 3
1 -> 4 -> 7 -> 9 -> 11
First pass returns 5. The length of the list.
We want to remove (5-3+1) = 3rd Node from the begining, which is 7
Second pass, make next of (5 - 3) 2nd node to point to (5-3+2) 4th node and we will have.
1 -> 4 -> 9 -> 11
Algorithm:
- Create a temporary node that points to head of the list.
- Get the length of the list on the first pass.
- Set pointer to temp node and move through list until we arrive at the (length - n) node, node previous the one we need to remove.
- Make next pointer of (length - n)th node to point to (length - n+2) node.
Code:
// Part of iq.opengenus.org
ListNode *removeNthNodeFromEnd(ListNode *head, int n){
//Check wheather the list is empty
if(!head)
return head;
//First pass to get length of the list
ListNode *temp = head;
int len = 0;
while(temp){
len += 1;
temp = temp->next;
}
//Index of node to be removed
int x = len - n;
// Initialize previous and current nodes
ListNode *currNode = head;
ListNode *prevNode = nullptr;
//Second pass to remove the node by shifting pointers.
while(x > 0){
prevNode = currNode;
currNode = currNode->next;
x -= 1;
}
//Condition if the head node is to be deleted.
if(!prevNode){
temp = currNode;
currNode = currNode->next;
delete temp;
head = currNode;
}else{
prevNode->next = currNode->next;
delete currNode;
}
return head;
}
Analysis
The procedure takes linear time, O(n) + O(n-x) = O(n). Getting the length of list and shifting pointers respectively.
O(1) space, no extra space is used.
Approach 2: Going through the list once, one pass
We first create two pointers, one fast and another slow which are n nodes apart from each other.
That is if the slow pointer is at the begining of the list, the fast pointer is at the n+1 position in the list.
In such a case, when the fast pointer arrives to the end of the list, the slow pointer will be at the nth node from end of list.
At this point we make the next pointer of node by slow pointer to point to next.next node, that is node after the next node.
Example;
List = [1, 4, 7, 9, 11]
n = 3
1 -> 4 -> 7 -> 9 -> 11
We want to remove 7
1 -> 4 -> 7 -> 9 -> 11, slow is at 4, fast is at 11.
There are n nodes between fast and slow.
When fast reached the end, slow points to nth node from end.
We make next of slow(4) point to next.next(9) thereby excluding 7.
The resulting list will be;
1 -> 4 -> 9 -> 11
Algorithm;
- Create two pointers fast pointer which points to (n-1)th node, slow points to 0th node.
- Go through linked list updating the two pointers.
- When the loop terminates fast.next == null, fast will be pointing to last node, slow will be at (n-1)th node from last node.
- Set next of slow pointer to next of next.
- Return head of list without deleted element.
Code:
// Part of iq.opengenus.org
ListNode *removeNthNodeFromEnd(ListNode *head, int n){
//Initialize fast and slow pointers
ListNode *fast = head, *slow = head;
//Give a headstart to fast pointer
for(int i = 0; i < n; i++)
fast = fast->next;
// If element to deleted is the head node
if(!fast)
return head->next;
//Move the pointers up to their respective positions
while(fast->next){
fast = fast->next;
slow = slow->next;
}
//Make next of slow to point to element after deleted element
slow->next = slow->next->next;
return head;
}
Analysis:
The time is linear O(n) n being length of linked list.
The space is O(1) as no extra space is used.
Questions:
- Why did we use the fast and slow pointers in the two pass approach?
- How can you compare linked lists to arrays, what are the advantages and disadvantages of each data structure, can you find situations where one would be better than the other?
