When we discuss removing the nth element from the end of the linked list, we’re essentially targeting the element positioned at the nth spot when counting backward from the end of the list. In simpler terms, it’s like removing the element that holds the nth position from the list’s tail. <\/p>\n\n\n\n
In this problem, we are given a linked list and a value of n and we have to remove a node that holds the nth position from the list\u2019s tail.<\/strong><\/p>\n\n\n\n Let us understand it better with an example:<\/p>\n\n\n\n List nodes = [1,2,3,4,5,6] The second node from the end has a value of 5, we will remove that node. So our output list becomes [1,2,3,4,6].<\/p>\n\n\n In the brute force approach to solve this problem, we have to first count the length of the linked list for this we have to traverse a linked list once to count the length and traverse again to delete the nth node, nth node from the last is the length – nth node from starting.<\/p>\n\n\n\n Steps to solve this problem:<\/p>\n\n\n\n The time complexity of the brute force approach is O(n), where n is the number of nodes in the linked list. The space complexity is O(1) as we haven\u2019t used any additional space.<\/p>\n\n\n\n We can avoid the hassle of counting the length of the list by using the two-pointers. Two-Pointers are a good approach to removing the nth node from the end of a linked list.<\/strong> Let’s see the steps of how we can solve this problem:<\/p>\n\n\n\n Below is the C++ program to remove the nth node from end of a list:<\/p>\n\n\n\n Here is the Python program for our problem:<\/p>\n\n\n\n You can implement it in Java too:<\/p>\n\n\n\n Output:<\/strong><\/p>\n\n\n\n The time complexity of this approach is O(n) as the code traverses the list once using two pointers (fast and slow) until the fast reaches the end. Here n is the number of nodes in the linked list.<\/p>\n\n\n\n The space complexity is O(1) as we haven\u2019t used any extra space.<\/p>\n\n\n\n Here is a small comparative analysis of both approaches:<\/p>\n\n\n\n
n = 2
Output = [1,2,3,4,6]<\/p>\n\n\n\n![\"Example](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-4-1024x373.png\")
<\/figure>\n<\/div>\n\n\nBrute Force Approach<\/strong><\/h2>\n\n\n\n
\n
![\"create](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-4-1024x215.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"move](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-4-1024x208.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"adjust](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-2-1024x227.png\")
<\/figure>\n<\/div>\n\n\nTwo Pointer Approach<\/strong><\/h2>\n\n\n\n
\n
![\"create](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-1-1024x185.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"create](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-1-1024x200.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"Move](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/7-1-1024x220.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"Move](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/8-1-1024x202.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"Remove](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/9-1-1024x221.png\")
<\/figure>\n<\/div>\n\n\nC++ Code<\/strong><\/h3>\n\n\n\n
#include <iostream>\n\n\/\/ Definition for singly-linked list.\nstruct ListNode {\n int val;\n ListNode* next;\n ListNode(int x) : val(x), next(nullptr) {}\n};\n\nListNode* removeNthFromEnd(ListNode* head, int n) {\n \/\/ Step 1: Create a new ListNode named 'start' with an empty value.\n ListNode* start = new ListNode(0);\n\n \/\/ Set the next 'start' to the head of the linked list.\n start->next = head;\n\n \/\/ Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.\n ListNode* fast = start;\n ListNode* slow = start;\n\n \/\/ Step 3: Move the 'fast' pointer n steps ahead in the linked list.\n for (int i = 0; i < n; i++) {\n fast = fast->next;\n }\n\n \/\/ Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.\n while (fast->next != nullptr) {\n slow = slow->next;\n fast = fast->next;\n }\n\n \/\/ Step 5: Remove the nth node from the end by adjusting pointers.\n slow->next = slow->next->next;\n\n \/\/ Step 6: Return the modified linked list starting from 'start->next'.\n return start->next;\n}\n\n\/\/ Function to print the linked list\nvoid printList(ListNode* head) {\n while (head != nullptr) {\n std::cout << head->val << " ";\n head = head->next;\n }\n std::cout << std::endl;\n}\n\nint main() {\n \/\/ Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6\n ListNode* head = new ListNode(1);\n head->next = new ListNode(2);\n head->next->next = new ListNode(3);\n head->next->next->next = new ListNode(4);\n head->next->next->next->next = new ListNode(5);\n head->next->next->next->next->next = new ListNode(6);\n\n std::cout << "Original Linked List: ";\n printList(head);\n\n int n = 2; \/\/ Example: Remove the 2nd node from the end\n\n \/\/ Remove the nth node from the end\n head = removeNthFromEnd(head, n);\n\n std::cout << "Modified Linked List: ";\n printList(head);\n\n return 0;\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
class ListNode:\n def __init__(self, x):\n self.val = x\n self.next = None\n\ndef removeNthFromEnd(head, n):\n # Step 1: Create a new ListNode named 'start' with an empty value.\n start = ListNode(0)\n # Set the next of 'start' to the head of the linked list.\n start.next = head\n\n # Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.\n fast = start\n slow = start\n\n # Step 3: Move the 'fast' pointer n steps ahead in the linked list.\n for _ in range(n):\n fast = fast.next\n\n # Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.\n while fast.next is not None:\n slow = slow.next\n fast = fast.next\n\n # Step 5: Remove the nth node from the end by adjusting pointers.\n slow.next = slow.next.next\n\n # Step 6: Return the modified linked list starting from 'start.next'.\n return start.next\n\n# Function to print the linked list\ndef printList(head):\n while head is not None:\n print(head.val, end=" ")\n head = head.next\n print()\n\n# Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6\nhead = ListNode(1)\nhead.next = ListNode(2)\nhead.next.next = ListNode(3)\nhead.next.next.next = ListNode(4)\nhead.next.next.next.next = ListNode(5)\nhead.next.next.next.next.next = ListNode(6)\n\nprint("Original Linked List:", end=" ")\nprintList(head)\n\nn = 2 # Example: Remove the 2nd node from the end\n\n# Remove the nth node from the end\nhead = removeNthFromEnd(head, n)\n\nprint("Modified Linked List:", end=" ")\nprintList(head)<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
class ListNode {\n int val;\n ListNode next;\n\n ListNode(int x) {\n val = x;\n next = null;\n }\n}\n\npublic class RemoveNthFromEnd {\n\n public static ListNode removeNthFromEnd(ListNode head, int n) {\n \/\/ Step 1: Create a new ListNode named 'start' with an empty value.\n ListNode start = new ListNode(0);\n \/\/ Set the next of 'start' to the head of the linked list.\n start.next = head;\n\n \/\/ Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.\n ListNode fast = start;\n ListNode slow = start;\n\n \/\/ Step 3: Move the 'fast' pointer n steps ahead in the linked list.\n for (int i = 0; i < n; i++) {\n fast = fast.next;\n }\n\n \/\/ Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.\n while (fast.next != null) {\n slow = slow.next;\n fast = fast.next;\n }\n\n \/\/ Step 5: Remove the nth node from the end by adjusting pointers.\n slow.next = slow.next.next;\n\n \/\/ Step 6: Return the modified linked list starting from 'start.next'.\n return start.next;\n }\n\n \/\/ Function to print the linked list\n public static void printList(ListNode head) {\n while (head != null) {\n System.out.print(head.val + " ");\n head = head.next;\n }\n System.out.println();\n }\n\n public static void main(String[] args) {\n \/\/ Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6\n ListNode head = new ListNode(1);\n head.next = new ListNode(2);\n head.next.next = new ListNode(3);\n head.next.next.next = new ListNode(4);\n head.next.next.next.next = new ListNode(5);\n head.next.next.next.next.next = new ListNode(6);\n\n System.out.print("Original Linked List: ");\n printList(head);\n\n int n = 2; \/\/ Example: Remove the 2nd node from the end\n\n \/\/ Remove the nth node from the end\n head = removeNthFromEnd(head, n);\n\n System.out.print("Modified Linked List: ");\n printList(head);\n }\n}<\/pre><\/div>\n\n\n\nOriginal Linked List: 1 2 3 4 5 6 \nModified Linked List: 1 2 3 4 6<\/code><\/pre>\n\n\n\n