Algorithm-Day30-Remove-Nth-Node-From-End-of-List-lc-19

Posted on In , Views:

🧩 Problem Description

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

💬 Example

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

💡 Intuition

Use the two-pointer technique:

  1. Move first pointer n steps ahead.
  2. Then move both first and second together until first reaches the end.
  3. Now second is just before the node to delete.

✅ Trick: use a dummy node before head to simplify edge cases like deleting the head.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy;
        ListNode second = dummy;

        // Move first n+1 steps to maintain gap
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // Move both pointers
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // Skip the target node
        second.next = second.next.next;

        return dummy.next;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(L), where L is the length of the list
  • Space Complexity: O(1)

✍️ Summary

  • Two-pointer pattern is super useful for problems involving relative positions.
  • Using a dummy node helps avoid corner-case bugs when deleting the head.
  • This technique appears frequently — make sure you’re confident with it.

Similar problems include:

  • lc-876: Middle of the Linked List
  • lc-160: Intersection of Two Linked Lists
  • lc-234: Palindrome Linked List