Welcome back, coders! Today, we’re tackling an interesting Linked List problem from LeetCode: **Remove the Nth Node from the End of a List**. This problem is a great introduction to the **two pointers technique**, which is not only elegant but also highly efficient for dealing with linked lists. Let’s dive into the problem, break down the solution, and write some code.

## Problem Description:

We’re given the **head** of a singly linked list and an integer **n**. The goal is to **remove the nth node from the end of the list** and return the modified list. You can read full description in LeetCode.com

For example:

`makefileCopy code````
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
```

In this example, we remove the 2nd node from the end, which is 4, and return the modified list.

## Approach Overview:

### 1. Understanding the Linked List:

In a linked list, every node points to the next node in the list, and the end is indicated by a `null`

reference. If we want to remove a node, we need to change the `next`

pointer of the previous node to skip over the node we want to remove.

### 2. Challenges:

The problem requires removing a node when we’re given its position from the **end** of the list. The trick here is that we cannot directly traverse backward in a singly linked list. So, how do we handle it?

### 3. Two-Pointer Technique:

To solve this, we can use a clever approach involving two pointers, often called **slow** and **fast**. Here’s the idea:

- We move the
`fast`

pointer**n+1**steps ahead. - Then, we move both
`fast`

and`slow`

pointers one step at a time until`fast`

reaches the end of the list. - When
`fast`

reaches the end, the`slow`

pointer will be just before the node we need to remove.

### 4. Using a Dummy Node:

To handle edge cases, such as removing the head node itself, we introduce a **dummy node** at the beginning of the list. This dummy node points to the head of the list and simplifies the logic for edge cases like removing the first node.

## Solution Code:

Here’s the Java solution using the two-pointer technique:

`/**`

* 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) {

// Create a dummy node to handle edge cases (like removing the head node)

ListNode dummy = new ListNode(0);

dummy.next = head;

// Initialize two pointers, both starting at the dummy node

ListNode fast = dummy;

ListNode slow = dummy;

// Move the fast pointer n+1 steps ahead

for (int i = 1; i <= n + 1; i++) {

fast = fast.next;

}

// Move both pointers one step at a time until fast reaches the end

while (fast != null) {

fast = fast.next;

slow = slow.next;

}

// Skip the nth node from the end by updating the next pointer

slow.next = slow.next.next;

// Return the modified list, which starts from dummy.next

return dummy.next;

}

}

## Step-by-Step Breakdown:

**Dummy Node Creation:**We create a`dummy`

node, which allows us to avoid special cases when removing the head. The`dummy`

node’s`next`

pointer is initialized to the`head`

of the list.**Initialize Two Pointers:**We initialize two pointers,`slow`

and`fast`

, both starting from the`dummy`

node.**Move the Fast Pointer Ahead:**The fast pointer is moved ahead by`n + 1`

positions. This ensures that when`fast`

reaches the end,`slow`

will be just before the node we want to remove.**Simultaneous Movement:**Once the fast pointer is ahead by`n + 1`

steps, we move both`slow`

and`fast`

pointers one step at a time. By the time the`fast`

pointer reaches the end, the`slow`

pointer will be just before the node we need to remove.**Skip the Target Node:**To remove the nth node, we simply update`slow.next`

to point to`slow.next.next`

, effectively skipping over the target node.**Return the Updated List:**Finally, we return`dummy.next`

, which is the head of the modified list.

## Time and Space Complexity:

**Time Complexity:**O(L), where L is the number of nodes in the list. We only traverse the list once with the two pointers.**Space Complexity:**O(1). We are only using a constant amount of extra space.

## Key Takeaways:

- The
**two-pointer technique**is a powerful tool for solving problems in linked lists where backward traversal isn’t an option. - Introducing a
**dummy node**simplifies edge case handling, especially when the node to be removed is the head of the list. - The solution runs in
**linear time**, making it optimal for larger lists.

## Conclusion:

This problem is a fantastic example of how a clever approach like the **two-pointer technique** can simplify a seemingly complex problem. By efficiently managing the traversal of the list, we can remove the nth node from the end in one pass, ensuring an optimal and elegant solution.

If you found this tutorial helpful, don’t forget to subscribe to our YouTube channel for more coding tutorials, and check out more content here on **SoundOfCode.com**. Happy coding!