Remove Nth Node From End of List

Problem Statement

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

Example 1

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

Example 2

Input: head = [1], n = 1
Output: []

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode first = dummy, 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;
    }
}

C++ Code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        ListNode* first = dummy;
        ListNode* second = dummy;

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

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

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

Python Code

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head

        first = dummy
        second = dummy

        for _ in range(n + 1):
            first = first.next

        while first:
            first = first.next
            second = second.next

        second.next = second.next.next
        return dummy.next

Javascript Code

var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode(-1);
    dummy.next = head;

    let first = dummy;
    let second = dummy;

    for (let 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;
};

Go Code

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{-1, head}

    first := dummy
    second := dummy

    for i := 0; i <= n; i++ {
        first = first.Next
    }

    for first != nil {
        first = first.Next
        second = second.Next
    }

    second.Next = second.Next.Next
    return dummy.Next
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the linked list. This is because we are iterating the entire linked list. But this is important to understand that this is one pass solution.
Space Complexity: O(1), we are not taking any extra space.