Remove Nth Node From End of List

Problem

Given a linked list, remove the nth node from the end of list and return its head.

Examples

Example 1:

graph TB;
	classDef royalBlueNode fill:#4169E1, color:#ffffff, stroke:#ffffff, stroke-width:2px;
	linkStyle default stroke:#FFD700, stroke-width:2px;
	classDef red fill:#FF6F61,stroke:#333, stroke:#ffffff, stroke-width:2px;
	subgraph G1[" "]
	   A(1):::royalBlueNode --- B(2):::royalBlueNode --- C(3):::royalBlueNode --- D(4):::red --- E(5):::royalBlueNode --- K("NULL")
	end
	
	subgraph G2[" "]
	   F(1):::royalBlueNode --- G(2):::royalBlueNode --- H(3):::royalBlueNode --- I(5):::royalBlueNode --- L("NULL")
	end
	
	
G1 --- G2	

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: Given linked list 1->2->3->4->5 and n = 2, the result is 1->2->3->5.

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/YQBnUXi-WII" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Reversing the list

Reversing the list changes the direction, making the nth node from the end become the nth node from the start of the reversed list. Once reversed, we can easily traverse forward to find and delete the required node.

Method 2 - Using the Length of the Linked List

1. Calculate the length of Linked List. Let the length be len.
2. Print the (len – n + 1)th node from the begining of the Linked List.

Code

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null)
        return null;

    //get length of list
    ListNode p = head;
    int len = 0;
    while (p != null) {
        len++;
        p = p.next;
    }

    //if remove first node
    int fromStart = len - n + 1;
    if (fromStart == 1)
        return head.next;

    //remove non-first node 
    p = head;
    int i = 0;
    while (p != null) {
        i++;
        if (i == fromStart - 1) {
            p.next = p.next.next;
        }
        p = p.next;
    }

    return head;
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)

Method 3 - One Pass - Using Slow and Fast Pointers

Utilize fast and slow pointers, positioning the fast pointer n steps ahead of the slow pointer. When the fast pointer reaches the end, the slow pointer will be at the element just before the target. This method is often referred to as the frame-based solution.

Dry Run

We can first run the code similar to [Find Nth Node From End Of Linked List](find-nth-node-from-end-of-linked-list), with some modifications. Firstly, we prepend the list with the dummy node, and slow pointer will point to it.

Code

Java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Create a dummy node to handle edge cases
        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 `first` and `second` 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; // Return the head of the modified linked list
    }
}

Python

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)  # Create a dummy node to handle edge cases
        first = dummy
        second = dummy
        
        # Move `first` pointer n + 1 steps ahead
        for _ in range(n + 1):
            first = first.next
        
        # Move `first` and `second` 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  # Return the head of the modified linked list

Complexity

• ⏰ Time complexity: O(n), n being the length of the linked list
• 🧺 Space complexity: O(1)

Method 4 - Recursion

Here found is passed by reference and is updated again and again. When we reach the end of the linked list, it is set to 1, otherwise it is incremented by 1.

Code

C

node * findNthNode(node * head, int find, int& found) {
    if (!head) {
        found = 1;
        return 0;
    }
    node * retval = findNthNode(head -> next, find, found);
    if (found == find)
        retval = head;
    found = found + 1;
    return retval;
}