Remove Nth Node From End of List

---

Remove Nth Node From End of List: 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: []

---

Example 3:

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

---

Constraints:

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

---

Try this Problem on your own or check similar problems:

1. Swapping Nodes in a Linked List
2. Delete the Middle Node of a Linked List

Solution:

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head);
    ListNode slow = dummy, fast = dummy;

    while(n-->0){
        fast = fast.next;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
}

JavaScript

/**
 * 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) {
  const dummy = new ListNode(-1, head);
  let slow = dummy;
  let fast = dummy;

  while (n-- > 0) {
    fast = fast.next;
  }
  while (fast.next !== null) {
    slow = slow.next;
    fast = fast.next;
  }

  slow.next = slow.next.next;
  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(-1, head)
        slow = dummy
        fast = dummy

        while n > 0:
            fast = fast.next
            n -= 1
        while fast.next is not None:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return dummy.next

C++

/**
 * 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(-1, head);
        ListNode* slow = dummy;
        ListNode* fast = dummy;

        while (n-- > 0) {
            fast = fast->next;
        }
        while (fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }

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

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We solve this problem using fast and slow pointers, if we move the fast pointer n nodes, and then move the fast and slow pointer simultaneously until we reach the end of the list (last element not the node null after it) we would make a difference of n nodes between slow and fast pointer. So the slow pointer would be pointing to the (n-1)th node (because we started from dummy node) from the end of the linked list which we have to remove. How do we remove the nth node? Well we just make the current node slow is pointing to, point to the element after the nth element with slow.next = slow.next.next; (basically skipping the nth element). Since the dummy.next is pointing to the head of the list with nth element from the end removed we just return it as the result.