Remove Nth Node From End Of List

                                            
/**
 * 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) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;

        for (int i = 0; i < n + 1; i++) {
            first = first->next;
        }

        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }

        second->next = second->next->next;
        return dummy->next;
    }
};

                                            
/**
 * 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) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode first = dummy;
        ListNode second = dummy;
        
        for(int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        
        while(first != null) {
            first = first.next;
            second = second.next;
        }
        
        second.next = second.next.next;
        
        return dummy.next;
    }
}

                                            
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        first = dummy
        second = dummy
        # Advances first pointer so that the gap between first and second is n nodes apart
        for i in range(1, n + 2):
            first = first.next
        # Move first to the end, maintaining the gap
        while first is not None:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* slow = dummy;
    struct ListNode* fast = dummy;

    for(int i = 0; i <= n; i++) {
        fast = fast->next;
    }

    while(fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    struct ListNode* temp = slow->next;
    slow->next = slow->next->next;
    free(temp);

    return dummy->next;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        second.next = second.next.next;
        
        return dummy.next;
    }
}

                                            
/**
 * 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 dummy = new ListNode(0);
    dummy.next = head;
    let first = dummy;
    let second = dummy;
    
    for (let i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    
    while (first !== null) {
        first = first.next;
        second = second.next;
    }
    
    second.next = second.next.next;
    
    return dummy.next;
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let dummy = new ListNode(0);
    dummy.next = head;
    let first: ListNode | null = dummy;
    let second: ListNode | null = dummy;

    for (let i = 1; i <= n + 1; i++) {
        if (first === null) return null;
        first = first.next;
    }

    while (first !== null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next!.next;

    return dummy.next;
}

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     */
    function removeNthFromEnd($head, $n) {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $first = $dummy;
        $second = $dummy;
        
        for ($i = 1; $i <= $n + 1; $i++) {
            $first = $first->next;
        }
        
        while ($first != null) {
            $first = $first->next;
            $second = $second->next;
        }
        
        $second->next = $second->next->next;
        
        return $dummy->next;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var dummyHead = ListNode(0)
        dummyHead.next = head
        
        var fast: ListNode? = dummyHead
        var slow: ListNode? = dummyHead
        
        for _ in 0..<n {
            fast = fast?.next
        }
        
        while fast?.next != nil {
            fast = fast?.next
            slow = slow?.next
        }
        
        slow?.next = slow?.next?.next
        
        return dummyHead.next
    }
}

                                            
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        var dummy = ListNode(0)
        dummy.next = head
        var first: ListNode? = dummy
        var second: ListNode? = dummy
        
        for (i in 1..n + 1) {
            first = first!!.next
        }
        
        while (first != null) {
            first = first.next
            second = second!!.next
        }
        
        second!!.next = second.next!!.next
        
        return dummy.next
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  ListNode? removeNthFromEnd(ListNode? head, int n) {
    ListNode? dummy = ListNode(0);
    dummy.next = head;
    ListNode? first = dummy;
    ListNode? second = dummy;
    
    for (int i = 0; i <= n; i++) {
      first = first!.next;
    }
    
    while (first != null) {
      first = first.next;
      second = second!.next;
    }
    
    second!.next = second.next!.next;
    
    return dummy.next;
  }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    first := head
    length := 0
    for first != nil {
        length++
        first = first.Next
    }
    length -= n
    first = dummy
    for length > 0 {
        length--
        first = first.Next
    }
    first.Next = first.Next.Next
    return dummy.Next
}

                                            
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @param {Integer} n
# @return {ListNode}
def remove_nth_from_end(head, n)
    dummy = ListNode.new
    dummy.next = head
    first = dummy
    second = dummy
    # Advances first pointer so that the gap between first and second is n nodes apart
    (n + 1).times do
        first = first.next
    end
    # Move first to the end, maintaining the gap
    while first != nil
        first = first.next
        second = second.next
    end
    # Remove the nth node from the end
    second.next = second.next.next
    return dummy.next
end

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
    def removeNthFromEnd(head: ListNode, n: Int): ListNode = {
        var dummy = new ListNode()
        dummy.next = head
        var fast = dummy
        var slow = dummy

        for (_ <- 1 to n + 1) {
            fast = fast.next
        }

        while (fast != null) {
            fast = fast.next
            slow = slow.next
        }

        slow.next = slow.next.next

        dummy.next
    }
}

                                            
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
  
impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut head = head;
        let mut fast = head.as_ref();
        let mut len = 0;
        
        while let Some(node) = fast {
            fast = node.next.as_ref();
            len += 1;
        }
        
        let mut dummy = ListNode { val: 0, next: head };
        let mut slow = &mut dummy;
        let nth = len - n;
        
        for _ in 0..nth {
            slow = slow.next.as_mut().unwrap();
        }
        
        slow.next = slow.next.as_mut().unwrap().next.take();
        
        dummy.next
    }
}

To solve this coding challenge, you need to remove the nth node from the end of a singly linked list and return the head of the list. Let's walk through the methodology and step-by-step pseudocode to achieve this efficiently.

Explanation

Initially, to solve this problem, it's important to understand the structure of a singly linked list. Each node in the list contains a value (

val

) and a reference to the next node (

next

). The key here is to remove the nth node from the end of the list, which is usually achieved with the help of two pointers. To accomplish this in one pass:

Use two pointers (
first

and
second

).
Move the
first

pointer
n+1

positions ahead so that when the
first

pointer reaches the end, the
second

pointer will be positioned right before the node to be removed.
Move both pointers one step at a time until the
first

pointer reaches the end of the list.
Adjust the
next

reference of the
second

pointer to skip the node to be removed.
Return the modified list's head.

By using a dummy node at the start, it simplifies scenarios where the head node itself might be removed.

Detailed Steps in Pseudocode

Let’s break it down step by step:

Setup and Initialization : Create a dummy node and set two pointers (
first

and
second

) to this dummy node.
Advance the
first

pointer : Move the
first

pointer
n + 1

steps ahead. This ensures that the
second

pointer will end up right before the node we need to remove.
Traverse the list : Move both pointers one step at a time until the
first

pointer reaches the end.
Remove the node : Adjust the
next

reference of the
second

pointer to skip over the target node.
Return the modified head : Return the
next

node of the dummy since the head could have been the one removed.

Let's translate these steps into detailed pseudocode:

Pseudocode

                                            
# Define a ListNode class (for context, definition only)
# class ListNode:
#     def __init__(self, value=0, next_node=None):
#         self.value = value
#         self.next = next_node

# Function to remove the nth node from the end of the list
function removeNthFromEnd(head, n):

# Step 1: Create a dummy node and set its next to the head of the list
dummy_node = new ListNode(0)
dummy_node.next = head

# Initialize two pointers, both starting from the dummy node
first_pointer = dummy_node
second_pointer = dummy_node

# Step 2: Move the first pointer n + 1 steps ahead
for i from 1 to n + 1 do
first_pointer = first_pointer.next

# Step 3: Move both pointers until the first pointer reaches the end
while first_pointer is not null do
first_pointer = first_pointer.next
second_pointer = second_pointer.next

# Step 4: Remove the nth node from the end
# second pointer is just before the node to be removed
second_pointer.next = second_pointer.next.next

# Step 5: Return the head of the modified list
return dummy_node.next

Step-by-Step Explanation in Pseudocode

Initialization :

Create a new dummy node and set its
next

to point to the head of the list.
Initialize two pointers,
first_pointer

and
second_pointer

, both pointing to the dummy node.

                                            
dummy_node = new ListNode(0)
dummy_node.next = head
first_pointer = dummy_node
second_pointer = dummy_node

Advance the first pointer :

Move the
first_pointer

n + 1

steps ahead to ensure a gap of
n

nodes.

                                            
for i from 1 to n + 1 do
first_pointer = first_pointer.next

Traverse the list :

Move both pointers one step at a time until
first_pointer

reaches the end of the list.

                                            
while first_pointer is not null do
first_pointer = first_pointer.next
second_pointer = second_pointer.next

Remove the nth node :

Adjust the
next

reference of
second_pointer

to skip the nth node.

                                            
second_pointer.next = second_pointer.next.next

Return the modified head :

Return the node following the dummy node.

                                            
return dummy_node.next

Understanding these detailed steps and the accompanying comments in the pseudocode should help in grasping the methodology to solve this linked list manipulation problem efficiently.