Remove Nth Node From End of List

class Solution {
public:
    ListNode* deleteNthFromEnd(ListNode* head, int n) {
        ListNode prehead(0);
        prehead.next = head;
        ListNode* lead = &prehead;
        ListNode* follow = &prehead;
        // Positioning lead pointer n+1 places from the start
        for (int i = 1; i <= n + 1; i++) {
            lead = lead->next;
        }
        // Moving both pointers until lead reaches the end
        while (lead != NULL) {
            lead = lead->next;
            follow = follow->next;
        }
        // Skipping the nth node from end
        follow->next = follow->next->next;
        return prehead.next;
    }
};

The solution provided details an implementation in C++ to remove the Nth node from the end of a singly linked list. The function deleteNthFromEnd receives the head of the list and the integer n, denoting the Nth position from the end of the list to be removed.

• Initialize a prehead to an auxiliary node with 0 as its value and set prehead.next to point to head. This helps simplify edge cases like removing the head.
• Create two pointers, lead and follow, initially set to point to the prehead.
• Increment the lead pointer n + 1 times. This positions it such that the gap between lead and follow is n nodes.
• Traverse the list with both pointers until lead reaches the end (NULL).
  • lead will move one node at a time.
  • follow will also move simultaneously with lead, maintaining the gap.
• After this loop, follow points to the node immediately before the Nth node from the end.
• To remove the Nth node, set follow.next to follow.next.next. This skips the desired node, effectively removing it.
• Finally, the function returns the next node of prehead, which is the potentially new head of the list (if the head was removed).

This solution operates in O(n) time complexity where n is the number of nodes in the list, as it requires a single pass to find and remove the specified node. The space complexity is O(1) since only a fixed number of extra pointers are used.

class Solution {
    public ListNode removeNthNodeFromEnd(ListNode startNode, int n) {
        ListNode temp = new ListNode(0);
        temp.next = startNode;
        ListNode front = temp;
        ListNode back = temp;
        
        for (int index = 1; index <= n + 1; index++) {
            front = front.next;
        }

        while (front != null) {
            front = front.next;
            back = back.next;
        }
        
        back.next = back.next.next;
        return temp.next;
    }
}

The provided Java solution addresses the common interview problem of removing the Nth node from the end of a singly linked list. Let's break down the approach:

• Initialize a dummy node (temp) and point its next to the starting node (startNode) of the list. This dummy node helps handle edge cases gracefully, such as removing the head of the list.
• Use two pointers, front and back, both starting at the dummy node. This maintains a gap of n nodes between them.
• Move the front pointer n + 1 times. This sets up the gap of n nodes since after moving n + 1 times, front is n nodes ahead of back.
• Traverse the list until front is null. For each step of front, move back one step. This keeps the gap consistent.
• After the loop, back.next is the node to be removed. Adjust pointers to exclude back.next from the list.
• Return the modified list starting from temp.next, skipping the dummy node.

This method efficiently finds and removes the Nth node with a single pass through the list, achieving O(n) time complexity where n is the number of nodes in the list. No extra space is used, yielding O(1) space complexity (ignoring the input). This solution leverages the two-pointer technique, which is effective in problems requiring elements at specific intervals or ends of a list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteNthNodeFromEnd(struct ListNode* head, int n) {
    struct ListNode placeholder;
    placeholder.val = 0;
    placeholder.next = head;
    struct ListNode* fast = &placeholder;
    struct ListNode* slow = &placeholder;
    // Pushes fast pointer ahead by n nodes to create the proper distance
    for (int i = 1; i <= n + 1; i++) fast = fast->next;
    // Traverse until fast reaches the tail, moving both pointers
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    // Skip the nth node from end
    slow->next = slow->next->next;
    return placeholder.next;
}

The problem involves removing the Nth node from the end of a singly-linked list in the C programming language. The function deleteNthNodeFromEnd accomplishes this by first establishing a placeholder node to handle potential edge cases like removing the head node of the list.

Here's the breakdown of the method used in the provided code:

• Begin by creating a placeholder node (placeholder) which points to the head of the list. This node acts as a starting point, ensuring the head is easily removable if needed.
• Define two pointers, fast and slow, both initially pointing to this placeholder node.
• Move the fast pointer forward by n+1 positions, creating a separation between the fast and slow pointers equal to n. This ensures that when fast pointer reaches the end of the list, slow pointer is right before the node to be removed.
• Traverse through the list until the fast pointer reaches the end, moving both fast and slow pointers forward consistently. At each step, fast moves one node ahead.
• Adjust the next pointer of the node at the slow pointer to skip the target node (the Nth node from the end), effectively removing it from the list.
• Return the next node of the placeholder, which now represents the possibly new head of the list after the removal operation.

This solution is efficient as it only requires a single pass through the list, making it O(n) in terms of time complexity, where n is the number of nodes in the list. The use of a placeholder node simplifies node removal operations, especially at boundary positions like the head of the list.

function deleteNthFromEnd(listHead, nth) {
    let prepNode = new ListNode(0);
    prepNode.next = listHead;
    let lead = prepNode;
    let trail = prepNode;

    for (let j = 1; j <= nth + 1; j++) {
        lead = lead.next;
    }
    
    while (lead !== null) {
        lead = lead.next;
        trail = trail.next;
    }
    
    trail.next = trail.next.next;
    return prepNode.next;
}

The provided JavaScript function deleteNthFromEnd efficiently removes the N-th node from the end of a singly linked list. The function takes two arguments: listHead, which is the head of the linked list, and nth, which specifies the position from the end of the list of the node to be removed.

Complete the task by following these steps:

1. Initialize a new dummy node (prepNode) and set its next pointer to the head of the list (listHead). This dummy node helps handle edge cases such as removing the head node.
2. Declare two pointer variables, lead and trail, and initially point them both to the dummy node.
3. Move the lead pointer forward by nth + 1 times. This step creates a gap between lead and trail pointers equal to nth + 1, positioning the lead pointer ahead so that when it reaches the end of the list, trail points to the node just before the target node.
4. Proceed with a loop where both lead and trail move one node forward until lead reaches the end of the list.
5. When the loop completes, trail.next is the node to be removed. Bypass this node by updating trail.next to trail.next.next, effectively removing the target node from the list.
6. Finally, return the new head of the list, which is prepNode.next, as the dummy node should not be part of the returned list.

This approach ensures that the function works in a single pass through the list, making it efficient with a time complexity of O(n) and a spatial complexity of O(1), where n is the number of nodes in the linked list.

class Solution:
    def deleteNthFromEnd(self, head_node, n):
        """
        :type head_node: ListNode
        :type n: int
        :rtype: ListNode
        """
        buffer_node = ListNode(0)
        buffer_node.next = head_node
        leading = buffer_node
        trailing = buffer_node
        # Advances leading pointer by n+1 steps ahead
        for i in range(n + 1):
            leading = leading.next
        # Proceed leading to the end while moving trailing
        while leading is not None:
            leading = leading.next
            trailing = trailing.next
        # Skipping the nth node from end
        trailing.next = trailing.next.next
        return buffer_node.next

This Python function provided, deleteNthFromEnd, removes the nth node from the end of a singly linked list and returns the modified list. Understand the following key points for implementing the function effectively:

1. Initially, a dummy node, buffer_node, is created and points to the head of the list. This node helps in edge cases, such as when the list has only one node or when removing the head node itself.
2. Both leading and trailing pointers start at the dummy node.
3. Move the leading pointer forward by n + 1 positions to create a gap between leading and trailing. This gap reflects the nth position from the end as leading moves.
4. Traverse through the list until leading points to None. During this traverse, both leading and trailing pointers move forward one step at a time, maintaining the gap.
5. Once leading reaches the end of the list, adjust the next pointer of the trailing node to skip the nth node from the end, effectively removing it.
6. Return the list starting from the next node of the dummy, which accounts for any changes made to the head during the process.

Implement these steps to modify any singly linked list by removing a designated node from its end without having to calculate the list's length.