algoadvance

Leetcode 19. Remove Nth Node From End of List

Problem Statement

You are given the head of a linked list, and an integer n. Remove the nth node from the end of the list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Constraints:

1. The number of nodes in the list is sz.
2. 1 <= sz <= 30
3. 0 <= Node.val <= 100
4. 1 <= n <= sz

Clarifying Questions

1. Q: Can we assume that the given linked list is always valid and non-empty? A: Yes, the constraints ensure that the list contains at least one node.

2. Q: What should we return if n equals the length of the linked list? A: We should remove the head of the list.

3. Q: Can n be zero or out of range? A: No, according to the constraints 1 <= n <= sz.

Strategy

1. Two-Pointer Approach (Fast and Slow)
   • Use two pointers: fast and slow.
   • Move the fast pointer n steps ahead first.
   • Move both fast and slow simultaneously until fast reaches the end of the list.
   • Remove the node after the slow pointer.
2. Steps:
   • Create a dummy node and point its next to the head (to handle edge case easily).
   • Initialize both fast and slow to the dummy node.
   • Move fast n steps forward.
   • Move both fast and slow simultaneously until fast.next is null.
   • Set slow.next to slow.next.next to bypass the node to be removed.
   • Return dummy.next.

Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Create a dummy node and point its next to head
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // Initialize the fast and slow pointers
        ListNode fast = dummy;
        ListNode slow = dummy;

        // Move the fast pointer n steps ahead
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // Move both pointers until the fast.next is null
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // Remove the nth node from end
        slow.next = slow.next.next;

        // Return the head which dummy.next points to
        return dummy.next;
    }
}

Time Complexity

• Time Complexity: O(L), where L is the length of the linked list. This is because we are traversing the list twice in succession (once for fast pointer moving n steps and another traversal for both pointers).
• Space Complexity: O(1), as we are using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?