Delete Nth node from the end of the given linked list
Given a linked list and an integer N, the task is to delete the Nth node from the end of the given linked list.
Examples:
Input: 2 -> 3 -> 1 -> 7 -> NULL, N = 1
Output:
The created linked list is:
2 3 1 7
The linked list after deletion is:
2 3 1Input: 1 -> 2 -> 3 -> 4 -> NULL, N = 4
Output:
The created linked list is:
1 2 3 4
The linked list after deletion is:
2 3 4
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Intuition:
Lets K be the total nodes in the linked list.
Observation : The Nthnode from the end is (K-N+1)th node from the beginning.
So the problem simplifies down to that we have to find (K-N+1)th node from the beginning.
- One way of doing it is to find the length (K) of the linked list in one pass and then in the second pass move (K-N+1) step from the beginning to reach the Nthnode from the end.
- To do it in one pass. Let’s take the first pointer and move N step from the beginning. Now the first pointer is (K-N+1) steps away from the last node, which is the same number of steps the second pointer require to move from the beginning to reach the Nth node from the end.
Approach:
- Take two pointers; the first will point to the head of the linked list and the second will point to the Nth node from the beginning.
- Now keep incrementing both the pointers by one at the same time until the second is pointing to the last node of the linked list.
- After the operations from the previous step, the first pointer should point to the Nth node from the end now. So, delete the node the first pointer is pointing to.
Below is the implementation of the above approach:
C++
|
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; class LinkedList { public:
// Linked list Node class Node { public: int data; Node* next; Node(int d) { data = d; next = NULL; } };
// Head of list Node* head; // Function to delete the nth node from // the end of the given linked list Node* deleteNode(int key) { // We will be using this pointer for holding // address temporarily while we delete the node Node *temp;
// First pointer will point to // the head of the linked list Node *first = head; // Second pointer will point to the // Nth node from the beginning Node *second = head; for (int i = 0; i < key; i++) { // If count of nodes in the given // linked list is <= N if (second->next == NULL) { // If count = N i.e. // delete the head node if (i == key - 1){ temp = head; head = head->next; free (temp); } return head; } second = second->next; } // Increment both the pointers by one until // second pointer reaches the end while (second->next != NULL) { first = first->next; second = second->next; } // First must be pointing to the // Nth node from the end by now // So, delete the node first is pointing to temp = first->next; first->next = first->next->next; free (temp); return head; } // Function to insert a new Node // at front of the list Node* push(int new_data) { Node* new_node = new Node(new_data); new_node->next = head; head = new_node; return head; } // Function to print the linked list void printList() { Node* tnode = head; while (tnode != NULL) { cout << (tnode->data) << ( " "); tnode = tnode->next; } } }; // Driver code int main() { LinkedList* llist = new LinkedList(); llist->head = llist->push(7); llist->head = llist->push(1); llist->head = llist->push(3); llist->head = llist->push(2); cout << ("Created Linked list is:\n"); llist->printList(); int N = 1; llist->head = llist->deleteNode(N); cout << ("\nLinked List after Deletion is:\n"); llist->printList(); } // This code is contributed by Arnab Kundu |
Java
|
// Java implementation of the approach class LinkedList { // Head of list Node head; // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to delete the nth node from // the end of the given linked list void deleteNode(int key) { // First pointer will point to // the head of the linked list Node first = head; // Second pointer will point to the // Nth node from the beginning Node second = head; for (int i = 0; i < key; i++) { // If count of nodes in the given // linked list is <= N if (second.next == null) { // If count = N i.e. delete the head node if (i == key - 1) head = head.next; return; } second = second.next; } // Increment both the pointers by one until // second pointer reaches the end while (second.next != null) { first = first.next; second = second.next; } // First must be pointing to the // Nth node from the end by now // So, delete the node first is pointing to first.next = first.next.next; } // Function to insert a new Node at front of the list public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print the linked list public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data + " "); tnode = tnode.next; } } // Driver code public static void main(String[] args) { LinkedList llist = new LinkedList(); llist.push(7); llist.push(1); llist.push(3); llist.push(2); System.out.println("\nCreated Linked list is:"); llist.printList(); int N = 1; llist.deleteNode(N); System.out.println("\nLinked List after Deletion is:"); llist.printList(); } } |
Python3
|
# Python3 implementation of the approach class Node: def __init__(self, new_data): self.data = new_data self.next = None class LinkedList: def __init__(self): self.head = None # createNode and and make linked list def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def deleteNode(self, n): first = self.head second = self.head for i in range(n):
# If count of nodes in the # given list is less than 'n' if(second.next == None):
# If index = n then # delete the head node if(i == n - 1): self.head = self.head.next return self.head second = second.next
while(second.next != None): second = second.next first = first.next
first.next = first.next.next
def printList(self): tmp_head = self.head while(tmp_head != None): print(tmp_head.data, end = ' ') tmp_head = tmp_head.next
# Driver Code llist = LinkedList() llist.push(7) llist.push(1) llist.push(3) llist.push(2) print("Created Linked list is:") llist.printList() llist.deleteNode(1) print("\nLinked List after Deletion is:") llist.printList() # This code is contributed by RaviParkash |
C#
|
// C# implementation of the approach using System;
public class LinkedList { // Head of list public Node head; // Linked list Node public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Function to delete the nth node from // the end of the given linked list void deleteNode(int key) { // First pointer will point to // the head of the linked list Node first = head; // Second pointer will point to the // Nth node from the beginning Node second = head; for (int i = 0; i < key; i++) { // If count of nodes in the given // linked list is <= N if (second.next == null) { // If count = N i.e. delete the head node if (i == key - 1) head = head.next; return; } second = second.next; } // Increment both the pointers by one until // second pointer reaches the end while (second.next != null) { first = first.next; second = second.next; } // First must be pointing to the // Nth node from the end by now // So, delete the node first is pointing to first.next = first.next.next; } // Function to insert a new Node at front of the list public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print the linked list public void printList() { Node tnode = head; while (tnode != null) { Console.Write(tnode.data + " "); tnode = tnode.next; } } // Driver code public static void Main(String[] args) { LinkedList llist = new LinkedList(); llist.push(7); llist.push(1); llist.push(3); llist.push(2); Console.WriteLine("\nCreated Linked list is:"); llist.printList(); int N = 1; llist.deleteNode(N); Console.WriteLine("\nLinked List after Deletion is:"); llist.printList(); } } // This code is contributed by 29AjayKumar |
Javascript
|
<script> // javascript implementation of the approach // Head of list var head; // Linked list Node class Node { constructor(val) { this.data = val; this.next = null; } } // Function to delete the nth node from // the end of the given linked list function deleteNode(key) { // First pointer will point to // the head of the linked list var first = head; // Second pointer will point to the // Nth node from the beginning var second = head; for (i = 0; i < key; i++) { // If count of nodes in the given // linked list is <= N if (second.next == null) { // If count = N i.e. delete the head node if (i == key - 1) head = head.next; return; } second = second.next; } // Increment both the pointers by one until // second pointer reaches the end while (second.next != null) { first = first.next; second = second.next; } // First must be pointing to the // Nth node from the end by now // So, delete the node first is pointing to first.next = first.next.next; } // Function to insert a new Node at front of the list function push(new_data) { var new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print the linked list function printList() { var tnode = head; while (tnode != null) { document.write(tnode.data + " "); tnode = tnode.next; } } // Driver code
push(7); push(1); push(3); push(2); document.write("\nCreated Linked list is:<br/>"); printList(); var N = 1; deleteNode(N); document.write("<br/>Linked List after Deletion is:<br/>"); printList(); // This code is contributed by todaysgaurav </script> |
Output Created Linked list is: 2 3 1 7 Linked List after Deletion is: 2 3 1
we already covered the iterative version above,
Now let us see its recursive approach as well,
Recursive Approach :
1) Create a dummy node and create a link from dummy node to head node. i.e, dummy->next = head
2) Then we will use the recursion stack to keep track of elements that are being pushed in recursion calls.
3) While popping the elements from recursion stack, we will decrement the N(position of target node from the end of linked list) i.e, N = N-1.
4) When we reach (N==0) that means we have reached at the target node,
5) But here is the catch, to delete the target node we require its previous node,
6) So we will now stop when (N==-1) i.e, we reached the previous node.
7) Now it is very simple to delete the node by using previousNode->next = previousNode->next->next.
C++
|
// C++ implementation of the approach // Code is contributed by Paras Saini #include <bits/stdc++.h> using namespace std; class LinkedList { public: int val; LinkedList* next; LinkedList() { this->next = NULL; this->val = 0; } LinkedList(int val) { this->next = NULL; this->val = val; } LinkedList* addNode(int val) { if (this == NULL) { return new LinkedList(val); } else { LinkedList* ptr = this; while (ptr->next) { ptr = ptr->next; } ptr->next = new LinkedList(val); return this; } } void removeNthNodeFromEndHelper(LinkedList* head, int& n) { if (!head) return; // Adding the elements in the recursion // stack removeNthNodeFromEndHelper(head->next, n); // Popping the elements from recursion stack n -= 1; // If we reach the previous of target node if (n == -1){ LinkedList* temp = head->next; head->next = head->next->next; free (temp); } } LinkedList* removeNthNodeFromEnd(int n) { // return NULL if we have NULL head or only // one node. if (!this or !this->next) return NULL; // Create a dummy node and point its next to // head. LinkedList* dummy = new LinkedList(); dummy->next = this; // Call function to remove Nth node from end removeNthNodeFromEndHelper(dummy, n); // Return new head i.e, dummy->next return dummy->next; } void printLinkedList() { if (!this) { cout << "Empty List\n"; return; } LinkedList* ptr = this; while (ptr) { cout << ptr->val << " "; ptr = ptr->next; } cout << endl; } }; class TestCase { private: void printOutput(LinkedList* head) { // Output: if (!head) cout << "Empty Linked List\n"; else head->printLinkedList(); } void testCase1() { LinkedList* head = new LinkedList(1); head = head->addNode(2); head = head->addNode(3); head = head->addNode(4); head = head->addNode(5); head->printLinkedList(); // Print: 1 2 3 4 5 head = head->removeNthNodeFromEnd(2); printOutput(head); // Output: 1 2 3 5 } void testCase2() { // Important Edge Case, where linkedList [1] // and n=1, LinkedList* head = new LinkedList(1); head->printLinkedList(); // Print: 1 head = head->removeNthNodeFromEnd(2); printOutput(head); // Output: Empty Linked List } void testCase3() { LinkedList* head = new LinkedList(1); head = head->addNode(2); head->printLinkedList(); // Print: 1 2 head = head->removeNthNodeFromEnd(1); printOutput(head); // Output: 1 } public: void executeTestCases() { testCase1(); testCase2(); testCase3(); } }; int main() { TestCase testCase; testCase.executeTestCases(); return 0; } |
Output 1 2 3 4 5 1 2 3 5 1 Empty Linked List 1 2 1
Two Pointer Approach – Slow and Fast Pointers
This problem can be solved by using two pointer approach as below:
- Take two pointers – fast and slow. And initialize their values as head node
- Iterate fast pointer till the value of n.
- Now, start iteration of fast pointer till the None value of the linked list. Also, iterate slow pointer.
- Hence, once the fast pointer will reach to the end the slow pointer will reach the node which you want to delete.
- Replace the next node of the slow pointer with the next to next node of the slow pointer.
Python
|
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node def display(self): temp = self.head while temp != None: print(temp.data) temp = temp.next def deleteNthNodeFromEnd(self, head, n): fast = head slow = head for _ in range(n): fast = fast.next if not fast: return head.next while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head if __name__ == '__main__': l = LinkedList() l.push(5) l.push(4) l.push(3) l.push(2) l.push(1) print('***** Linked List Before deletion *****') l.display() print('************** Delete nth Node from the End *****') l.deleteNthNodeFromEnd(l.head, 2) print('*********** Linked List after Deletion *****') l.display() |
Output ***** Linked List Before deletion ***** 1 2 3 4 5 ************** Delete nth Node from the End ***** *********** Linked List after Deletion ***** 1 2 3 5
Time complexity: O(n)
Article Tags :
Linked List
Delete a Linked List
Traversal
Practice Tags :
Linked List
Traversal
Read Full Article
Remove Nth node from end of the Linked List
Given a linked list. The task is to remove the Nth node from the end of the linked list.
Examples:
Input : 1->2->3->4->5 , N = 2
Output : 1->2->3->5Input : 7->8->4->3->2 , N = 1
Output : 7->8->4->3
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Prerequisites:
1. Delete a node from the linked list.
2. Find the nth node from the end of the linked list
Approach:
Deleting the Bth node from last is basically the same as deleting (length-B+1) from the start. In our approach, first, we evaluate the length of the linked list, then check
- If length < B, then we can’t remove the node
- If length = B, then return head->next
- If length > B, then it means we have to delete the intermediate node, we will delete this node and make its prev node point to the next node of the deleted node.
C
|
// C program to delete nth node from last #include<stdio.h> #include<stdlib.h> // Structure of node struct Node { int data; struct Node* next; }; // Function to insert node in a linked list struct Node* create(struct Node* head, int x) { struct Node *temp, *ptr = head; temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = x; temp->next = NULL; if (head == NULL) head = temp; else { while (ptr->next != NULL) { ptr = ptr->next; } ptr->next = temp; } return head; } // Function to remove nth node from last struct Node* removeNthFromEnd(struct Node* head, int B) { // To store length of the linked list int len = 0; struct Node* tmp = head; while (tmp != NULL) { len++; tmp = tmp->next; } // B > length, then we can't remove node if (B > len) { printf( "Length of the linked list is %d",len ); printf( " we can't remove %dth node from the",B); printf(" linked list\n"); return head; } // We need to remove head node else if (B == len) { // Return head->next return head->next; } else { // Remove len - B th node from starting int diff = len - B; struct Node* prev= NULL; struct Node* curr = head; for(int i = 0;i < diff;i++){ prev = curr; curr = curr->next; } prev->next = curr->next; return head; } } // This function prints contents of linked // list starting from the given node void display(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ",temp->data); temp = temp->next; } printf("\n"); } // Driver code int main() { struct Node* head = NULL; head = create(head, 1); head = create(head, 2); head = create(head, 3); head = create(head, 4); head = create(head, 5); int n = 2; printf("Linked list before modification: \n"); display(head); head = removeNthFromEnd(head, 2); printf("Linked list after modification: \n"); display(head); return 0; } |
C++
|
// CPP program to delete nth node from last #include <bits/stdc++.h> using namespace std; // Structure of node struct Node { int data; struct Node* next; }; // Function to insert node in a linked list struct Node* create(struct Node* head, int x) { struct Node *temp, *ptr = head; temp = new Node(); temp->data = x; temp->next = NULL; if (head == NULL) head = temp; else { while (ptr->next != NULL) { ptr = ptr->next; } ptr->next = temp; } return head; } // Function to remove nth node from last Node* removeNthFromEnd(Node* head, int B) { // To store length of the linked list int len = 0; Node* tmp = head; while (tmp != NULL) { len++; tmp = tmp->next; }
// B > length, then we can't remove node if (B > len) { cout << "Length of the linked list is " << len; cout << " we can't remove "<< B << "th node from the"; cout << " linked list\n"; return head; }
// We need to remove head node else if (B == len) {
// Return head->next return head->next;
} else { // Remove len - B th node from starting int diff = len - B; Node* prev= NULL; Node* curr = head; for(int i = 0;i < diff;i++){ prev = curr; curr = curr->next; } prev->next = curr->next; return head; }
} // This function prints contents of linked // list starting from the given node void display(struct Node* head) { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } cout << endl; } // Driver code int main() { struct Node* head = NULL;
head = create(head, 1); head = create(head, 2); head = create(head, 3); head = create(head, 4); head = create(head, 5);
int n = 2;
cout << "Linked list before modification: \n"; display(head); head = removeNthFromEnd(head, 2); cout << "Linked list after modification: \n"; display(head); return 0; } |
Java
|
// Java program to delete nth node from last class GFG { // Structure of node static class Node { int data; Node next; }; // Function to insert node in a linked list static Node create(Node head, int x) { Node temp, ptr = head; temp = new Node(); temp.data = x; temp.next = null; if (head == null) head = temp; else { while (ptr.next != null) { ptr = ptr.next; } ptr.next = temp; } return head; } // Function to remove nth node from last static Node removeNthFromEnd(Node head, int B) { // To store length of the linked list int len = 0; Node tmp = head; while (tmp != null) { len++; tmp = tmp.next; }
// B > length, then we can't remove node if (B > len) { System.out.print("Length of the linked list is " + len); System.out.print(" we can't remove "+ B + "th node from the"); System.out.print(" linked list\n"); return head; }
// We need to remove head node else if (B == len) {
// Return head.next return head.next;
} else { // Remove len - B th node from starting int diff = len - B; Node prev= null; Node curr = head; for(int i = 0; i < diff; i++) { prev = curr; curr = curr.next; } prev.next = curr.next; return head; }
} // This function prints contents of linked // list starting from the given node static void display(Node head) { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } // Driver code public static void main(String[] args) { Node head = null;
head = create(head, 1); head = create(head, 2); head = create(head, 3); head = create(head, 4); head = create(head, 5);
int n = 2;
System.out.print("Linked list before modification: \n"); display(head); head = removeNthFromEnd(head, 2); System.out.print("Linked list after modification: \n"); display(head); } } // This code is contributed by Rajput-Ji |
Python3
|
# Python3 program to delete nth node from last class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to add node at the end def create(self, x): new_node = Node(x) if self.head is None: self.head = new_node return last = self.head while last.next: last = last.next last.next = new_node # This function prints contents of linked # list starting from the given node def display(self): temp = self.head while temp: print(temp.data, end = " ") temp = temp.next # Function to remove nth node from last def removeNthFromEnd(head, k):
# the function uses two pointer method first = head second = head count = 1 while count <= k: second = second.next count += 1 if second is None: head.value = head.next.value head.next = head.next.next return while second.next is not None: first = first.next second = second.next first.next = first.next.next # Driver code # val list contains list of values val = [1, 2, 3, 4, 5] k = 2 ll = LinkedList() for i in val: ll.create(i) print("Linked list before modification:"); ll.display() removeNthFromEnd(ll.head, k) print("\nLinked list after modification:"); ll.display() # This code is contributed by Dhinesh |
C#
|
// C# program to delete nth node from last using System;
class GFG { // Structure of node class Node { public int data; public Node next; }; // Function to insert node in a linked list static Node create(Node head, int x) { Node temp, ptr = head; temp = new Node(); temp.data = x; temp.next = null; if (head == null) head = temp; else { while (ptr.next != null) { ptr = ptr.next; } ptr.next = temp; } return head; } // Function to remove nth node from last static Node removeNthFromEnd(Node head, int B) { // To store length of the linked list int len = 0; Node tmp = head; while (tmp != null) { len++; tmp = tmp.next; }
// B > length, then we can't remove node if (B > len) { Console.Write("Length of the linked list is " + len); Console.Write(" we can't remove " + B + "th node from the"); Console.Write(" linked list\n"); return head; }
// We need to remove head node else if (B == len) {
// Return head.next return head.next;
} else { // Remove len - B th node from starting int diff = len - B; Node prev= null; Node curr = head; for(int i = 0; i < diff; i++) { prev = curr; curr = curr.next; } prev.next = curr.next; return head; }
} // This function prints contents of linked // list starting from the given node static void display(Node head) { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.Write("\n"); } // Driver code public static void Main(String[] args) { Node head = null;
head = create(head, 1); head = create(head, 2); head = create(head, 3); head = create(head, 4); head = create(head, 5);
Console.Write("Linked list before modification: \n"); display(head); head = removeNthFromEnd(head, 2); Console.Write("Linked list after modification: \n"); display(head); } } // This code is contributed by 29AjayKumar |
Javascript
|
<script> // javascript program to delete nth node from last // Structure of node class Node { constructor() { this.data = 0; this.next = null; } } // Function to insert node in a linked list function create(head , x) { var temp, ptr = head; temp = new Node(); temp.data = x; temp.next = null; if (head == null) head = temp; else { while (ptr.next != null) { ptr = ptr.next; } ptr.next = temp; } return head; } // Function to remove nth node from last function removeNthFromEnd(head , B) { // To store length of the linked list var len = 0; var tmp = head; while (tmp != null) { len++; tmp = tmp.next; } // B > length, then we can't remove node if (B > len) { document.write("Length of the linked list is " + len); document.write(" we can't remove " + B + "th node from the"); document.write(" linked list\n"); return head; } // We need to remove head node else if (B == len) { // Return head.next return head.next; } else { // Remove len - B th node from starting var diff = len - B; var prev = null; var curr = head; for (i = 0; i < diff; i++) { prev = curr; curr = curr.next; } prev.next = curr.next; return head; } } // This function prints contents of linked // list starting from the given node function display(head) { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write("<br/>"); } // Driver code
var head = null; head = create(head, 1); head = create(head, 2); head = create(head, 3); head = create(head, 4); head = create(head, 5); var n = 2; document.write("Linked list before modification: <br/>"); display(head); head = removeNthFromEnd(head, 2); document.write("Linked list after modification: <br/>"); display(head); // This code contributed by Rajput-Ji </script> |
Output Linked list before modification: 1 2 3 4 5 Linked list after modification: 1 2 3 5
Another Approach: Two Pointer Approach
Deleting the Bth node from last is basically the same as deleting (length-B+1) from the start. In our approach, we will define 2 pointers, fast pointer and slow pointer.
Algorithm:
- Take two Node slowPtr and fastPtr, such that next points to the head
- Take one Node to store the head, initially it’s a dummy node(start), and the next of the node will be pointing to the head. The dummy node is taken to handle the edge case where B=N(size of the LinkedList)
- Start traversing until the fast pointer reaches the nth node
for(int i = 0; i < B; i++){
fastPtr = fastPtr->next;
} - Start traversing by one step both of the pointers until the fast pointers reach the end
while(fastPtr->next != NULL)
{
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
} - When the traversal is done, delete the next node to slowPtr
slow->next = slow->next->next; - Return the next of start
return start->next;
C++
|
// CPP program to delete nth node from last #include <bits/stdc++.h> using namespace std; // Structure of node struct Node { int data; struct Node* next; }; // Function to insert node in a linked list struct Node* create(struct Node* head, int x) { struct Node *temp, *ptr = head; temp = new Node(); temp->data = x; temp->next = NULL; if (head == NULL) head = temp; else { while (ptr->next != NULL) { ptr = ptr->next; } ptr->next = temp; } return head; } // Function to remove nth node from last Node* removeNthFromEnd(Node* head, int B) { Node *start = new Node(); start -> next = head; Node* fastPtr = start; Node* slowPtr = start;
// Traverse the LinkedList B times for(int i = 0; i < B; i++){ fastPtr = fastPtr->next; }
//Increase the slow pointer while(fastPtr->next != NULL) { fastPtr = fastPtr->next; slowPtr = slowPtr->next; }
//Deletion step slowPtr->next = slowPtr->next->next;
//Return head return start->next; } // This function prints contents of linked // list starting from the given node void display(struct Node* head) { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } cout << endl; } // Driver code int main() { struct Node* head = NULL;
head = create(head, 1); head = create(head, 2); head = create(head, 3); head = create(head, 4); head = create(head, 5);
int n = 2;
cout << "Linked list before modification: \n"; display(head); head = removeNthFromEnd(head, 2); cout << "Linked list after modification: \n"; display(head); return 0; } |
Output Linked list before modification: 1 2 3 4 5 Linked list after modification: 1 2 3 5
Article Tags :
Linked List
Mathematical
Traversal
Practice Tags :
Linked List
Mathematical
Traversal
Read Full Article
Deletion in doubly linked list at the end
Deletion of the last node in a doubly linked list needs traversing the list in order to reach the last node of the list and then make pointer adjustments at that position.
In order to delete the last node of the list, we need to follow the following steps.
- If the list is already empty then the condition head == NULL will become true and therefore the operation can not be carried on.
- If there is only one node in the list then the condition head → next == NULL become true. In this case, we just need to assign the head of the list to NULL and free head in order to completely delete the list.
- Otherwise, just traverse the list to reach the last node of the list. This will be done by using the following statements.
- The ptr would point to the last node of the ist at the end of the for loop. Just make the next pointer of the previous node of ptr to NULL.
free the pointer as this the node which is to be deleted.
- Step 1: IF HEAD = NULL
- Step 2: SET TEMP = HEAD
- Step 3: REPEAT STEP 4 WHILE TEMP->NEXT != NULL
- Step 4: SET TEMP = TEMP->NEXT
- Step 5: SET TEMP ->PREV-> NEXT = NULL
- Step 6: FREE TEMP
- Step 7: EXIT
Write UNDERFLOW
Go to Step 7
[END OF IF]
[END OF LOOP]
Remove Nth Node From End of List
Difficulty: Medium
Asked in: Google, Amazon
Understanding the problem
Problem Description: You are given a linked list, write a program to remove the nth node from the end of the list and return the head.
Problem Note:
- It is guaranteed that n ≤ length of linked list
- Try to do this in one iteration.
Example 1
Input: 2->6->1->9, n=2 Output: 2->6->9Example 2
Input: 1->2->3->4, n=4 Output: 2->3->4Example 3
Input: 4->9->1->2, n=1 Output: 4->9->1The node structure given to you will be→
class ListNode { int val; ListNode next; ListNode(int x) { val = x } }Solutions
We will be discussing three different solutions
- Using Auxillary Space — By saving each node in an array
- Making two passes through the list — remove the length- nth from the beginning.
- Making one pass through the list — Using fast and slow pointers.
1. Using Auxillary Space
If we could save all the nodes in the array then, we could just remove the pointer of the (length-n-1)th node next to its next.next. In this way the nth node would be removed.
Pseudo CodeListNode removeNthFromEnd(ListNode head, int n) { ListNode list[] ListNode curr = head while(curr!=null){ list.append(curr) curr = curr.next } int size = size(list) if(size > 1){ if(size > n){ ListNode prev = list[size-n-1] ListNode next = null if(n > 1){ next = list[size-n+1] } prev.next = next; } else { head = list[1] } return head } return null }
Complexity Analysis
Time Complexity — O(n)
Space Complexity — O(n)
Critical Ideas to Thnik
- Why we are storing each node in an array?
- What will we return if the given value of n is 1?
- Why did we set the list[size-n-1]th node next pointer with list[size-n+1] ?
2. Making two passes through the list
You can conclude from the previous approach that we don’t actually need to store the nodes in the array as we only need the length — nth node.
So, we could say that the problem is simply reduced to: Remove the (L−n+1) th node from the beginning in the list, where L is the list length.
Solution Step
- Create a “dummy” node, which points to the list head.
- On the first pass, we find the list length L.
- Set a pointer to the dummy node and start to move it through the list until it comes to the (L−n)th node.
- Relink the next pointer of the (L−n)th node to the (L−n+2)th node.
Pseudo CodeListNode removeNthFromEnd(ListNode head, int n) { ListNode curr = head int end_index = 0 while(curr) { end_index += 1 curr = curr->next; } index_to_remove = end_index - n i = 0 curr = head ListNode prev = nullptr while(i < index_to_remove) { prev = curr curr = curr.next i += 1 } if(curr == head) { head = head.next } else if(prev) { prev.next = curr.next } delete curr return head }
Complexity Analysis
Time complexity: O(L) where L is the length of the linked list.
Space complexity: O(1)
Critical Ideas to Think
- What information about the list does the first pass give us?
- What does the prev pointer represent here?
- Can you dry run the above pseudo code with the above examples?
3. Making a single pass through the list
We could optimize the above approach where we only need a one-time traversal of the linked list. We could create two pointers, namely slow and a fast pointer pointing to the nodes that are n nodes apart from each other.
The fast pointer advances the list by n+1 steps from the beginning, while the slow pointer starts from the beginning of the list separating them by n nodes. We maintain this constant gap by advancing both pointers together until the fast pointer arrives past the last node. The slow pointer will be pointing at the nth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node’s next to the next node.
Solution steps
- Create a fast and slow pointer pointing to n-1th and 0th node of the linked list
- Start iterating over the linked list while updating the slow and fast pointers to its next.
- When the loop terminates, then the fast pointer would be pointing to the last node and slow would be pointing to n-1th from the last node.
- Set the next of slow pointer to its next of next
- Now return the head.
Pseudo CodeListNode* removeNthFromEnd(ListNode* head, int n) { ListNode fast = head ListNode dummy dummy->next = head ListNode slow = dummy int step_ahead = 0 while(step_ahead < n-1){ fast = fast.next step_ahead += 1 } while(fast->next!=NULL){ slow = slow.next fast = fast.next } //slow points to the node before target slow->next = slow->next->next return dummy->next }
Complexity Analysis
Time complexity: O(L) where L is the length of the linked list.
Space complexity: O(1)
Critical Ideas to Think
- What did we initialize the fast and slow pointers with and why?
- How does the algorithm work if the given value of n is 1?
- Can you dry run this algorithm for the above example and point out the difference between the single pass and double pass algorithms?
Comparison of Different Solutions
Suggested problems to Solve
- K reverse linked list
- Reverse a Link List
- Delete a Doubly Linked List node at a given position
- Recursively delete a kth node from a linked list
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!