Given a singly linked list, write a code to remove nth node from the end of a linked list. In this problem, you can assume the value of n is always valid.
For example –
In this example, the input linked list has four nodes and we have to remove 2nd node from the end.
Input –
15 -> 9 -> 8 -> 5 -> NULL , N = 2
After removing second node (node whose value is 8) from the end, the output is
15 -> 9 -> 5 -> NULL
We have discussed the problem statement. Let’s discuss multiple approaches and their time and space complexities to solve this problem.
Remove nth node from end of a linked list video tutorial
Remove Nth Node from End of a Linked List – Java Code
The easiest approach is to traverse a linked list twice to solve this problem.
In the first traversal, we count the number of nodes present in a linked list. Once we know the count of elements in a list, the next step is to remove the nth node from the end.
The time complexity of this approach is O(n) and its space complexity is O(1).
Let’s write its java code.
|
1 2 3 4 5 6 7 8 9 10 11 |
//Structure of node class public class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
//Remove node from end using two pass public class RemoveNodeFromEnd { public Node insertAtHead(Node head, int data) { if (head == null) { head = new Node(data); } else { // Create a new node Node temp = new Node(data); // New node points to head temp.next = head; // Head points to a new node head = temp; } return head; } public Node removeNodeFromEnd(Node head, int n) { Node temp = head; int len = 0; //Count number of nodes while(temp != null) { temp = temp.next; len++; } int pos = len-n+1; //If only one node is there in linked list if(pos == 1) { return head.next; } temp = head; len = 0; while(temp != null) { len++; if(pos-1 == len) { temp.next = temp.next.next; } temp = temp.next; } return head; } public void print(Node head) { Node temp = head; while (temp != null) { System.out.print(temp.data + " -> "); temp = temp.next; } System.out.print("null"); System.out.println(" "); } public static void main(String[] args) { Node head = null; RemoveNodeFromEnd ll = new RemoveNodeFromEnd(); head = ll.insertAtHead(head, 5); head = ll.insertAtHead(head, 8); head = ll.insertAtHead(head, 9); head = ll.insertAtHead(head, 15); System.out.println(" Linked List "); ll.print(head); Node result = ll.removeNodeFromEnd(head, 2); System.out.println(" After removing element "); ll.print(result); } } |
Programming questions on linked list
Programming questions on binary tree
Remove Nth Node from End of List in Single Traversal – Java Code
Let’s improve our previous solution and solve this problem in a single traversal. To solve this problem in a single traversal/pass we are going to use two pointers (slow and fast).
First, move the fast pointer by n steps. After that move fast and slow pointer by one step until fast pointer does not point to null.
When the fast pointer reaches the end the slow pointer is exactly the nth node from the end.
The time complexity of removing the nth node from the end is O(n) and its space complexity is O(1).
Remove duplicates from a sorted linked list
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//Single traversal java code public Node removeNodeFromEndSinglePass(Node head, int n) { //Declare two pointers Node slow = head; Node fast = head; //Move fast pointer by n steps for(int i = 1; i <= n; i++) { fast = fast.next; } /* Special handling, when only one node is present in a linked list */ if(fast == null) { head = head.next; return head; } while(fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; } |
Remove Nth Node from List End InterviewBit Solution – Java Code
The same problem is present in interviewbit where we have to remove the nth node from list end.
The only difference is, If the value of n is greater than the size of the list, then we have to remove the first node of the list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//Java Code public class Solution { public ListNode removeNthFromEnd(ListNode A, int B) { int count = 0; //Declare two pointers slow and fast ListNode slow = A; ListNode fast = A; while(count++ <= B && fast != null) { fast = fast.next; } /* If the value of B is greater the no. of elements present in a list then remove the first element of a linked list. */ if(count < B) return A.next; if(fast == null) return slow.next; while(fast != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return A; } } |
