19. Remove Nth Node From End of List

Intuition

The problem requires removing the nth node from the end of a linked list. To do this effectively, we need to know the position of the node relative to the start of the list. This can be achieved by calculating the total length of the list and using it to find the nth node from the end.

Approach

1. Calculate Length: Traverse the list to determine its total length.
2. Dummy Node: Introduce a dummy node to handle edge cases, such as removing the head of the list.
3. Find Target Node: Traverse the list again to find the node just before the nth node from the end.
4. Remove Node: Adjust the pointers to remove the target node.
5. Return Modified List: Return the head of the modified list, skipping the dummy node.

Complexity

Time Complexity:

O(L), where L is the length of the list. We traverse the list twice: once to calculate its length and once to locate the node to be removed.

Space Complexity:

O(1). We use a constant amount of additional space.

Code

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length = 0;
        ListNode* curr = head;
        
        // Calculate the length of the list
        while (curr != nullptr) {
            length++;
            curr = curr->next;
        }
        
        // Use a dummy node to simplify edge cases
        ListNode dummy(0, head);
        curr = &dummy;
        
        // Find the node just before the one we want to remove
        for (int i = 0; i < length - n; ++i) {
            curr = curr->next;
        }
        
        // Remove the nth node from the end
        if (curr->next != nullptr) {
            curr->next = curr->next->next;
        }
        
        return dummy.next;
    }
};

Python

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

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        curr = head
        
        # Calculate the length of the list
        while curr:
            length += 1
            curr = curr.next
        
        # Use a dummy node to simplify edge cases
        dummy = ListNode(0, head)
        curr = dummy
        
        # Find the node just before the one we want to remove
        for _ in range(length - n):
            curr = curr.next
        
        # Remove the nth node from the end
        if curr.next:
            curr.next = curr.next.next
        
        return dummy.next

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int length = 0;
        ListNode curr = head;
        
        // Calculate the length of the list
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        
        // Use a dummy node to simplify edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        curr = dummy;
        
        // Find the node just before the one we want to remove
        for (int i = 0; i < length - n; i++) {
            curr = curr.next;
        }
        
        // Remove the nth node from the end
        if (curr.next != null) {
            curr.next = curr.next.next;
        }
        
        return dummy.next;
    }
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    
    let length = 0
    let curr = head
    while(curr!=null) {
        length++
        curr = curr.next
    }
    let index = 0
    let dummy = new ListNode(0, head)
    curr = dummy
    while(curr!=null) {
        if(index==(length-n)) {
            curr.next = curr.next ? curr.next.next : null
            break
        }
        index++
        curr = curr.next
    }
    return dummy.next
};