Table of contents

Remove Nth node from the end of the linked list

Given a singly linked list, the task is to remove the nth node from the end of the list and return the head of the modified list. The value of n is guaranteed to be valid.

Input-Output Examples

Example 1:

  • Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, n = 2
  • Output: 1 -> 2 -> 3 -> 5 -> NULL (The 4th node from the end is removed)

Example 2:

  • Input: 1 -> 2 -> NULL, n = 1
  • Output: 1 -> NULL (The 1st node from the end is removed)

Example 3:

  • Input: 1 -> NULL, n = 1
  • Output: NULL (The only node is removed)

Approach:
Technique to be used: Two-pointer technique

To remove the nth node from the end of the linked list, we can use the two-pointer technique. The first pointer moves n steps ahead of the second pointer, ensuring that when the first pointer reaches the end of the list, the second pointer is at the node just before the nth node from the end.

Steps to implement:

  1. Initialize two pointers, first and second, both pointing to a dummy node that precedes the head of the list.
  2. Move the first pointer n+1 steps ahead.
  3. Move both pointers one step at a time until the first pointer reaches the end of the list.
  4. The second pointer will be at the node just before the nth node from the end.
  5. Adjust the next pointer of the second pointer to remove the nth node.
  6. Return the head of the modified list.

C++ Program to remove Nth node from the end of the Linked List

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* first = &dummy;
        ListNode* second = &dummy;
        
        // Move first pointer n+1 steps ahead
        for (int i = 0; i <= n; ++i) {
            first = first->next;
        }
        
        // Move both pointers until first reaches the end
        while (first != NULL) {
            first = first->next;
            second = second->next;
        }
        
        // Remove the nth node from the end
        second->next = second->next->next;
        
        return dummy.next;
    }
};

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    Solution sol;
    head = sol.removeNthFromEnd(head, 2);

    // Printing the modified linked list
    cout << "Modified list: ";
    printList(head);

    return 0;
}

Java Program to remove Nth node from the end of the Linked List

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        
        // Move first pointer n+1 steps ahead
        for (int i = 0; i <= n; ++i) {
            first = first.next;
        }
        
        // Move both pointers until first reaches the end
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        // Remove the nth node from the end
        second.next = second.next.next;
        
        return dummy.next;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        Solution sol = new Solution();
        head = sol.removeNthFromEnd(head, 2);

        // Printing the modified linked list
        System.out.print("Modified list: ");
        printList(head);
    }
}

Python Program to remove Nth node from the end of the Linked List

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy
        
        # Move first pointer n+1 steps ahead
        for _ in range(n + 1):
            first = first.next
        
        # Move both pointers until first reaches the end
        while first:
            first = first.next
            second = second.next
        
        # Remove the nth node from the end
        second.next = second.next.next
        
        return dummy.next

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

sol = Solution()
head = sol.removeNthFromEnd(head, 2)

# Printing the modified linked list
print("Modified list:", end=" ")
print_list(head)

DSA

Related Articles