This content originally appeared on DEV Community and was authored by Rohith V
Problem Statement
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Test Cases
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
Follow up: Could you do this in one pass?
Intuition
We need to know the previous node of the targeted node we will delete, ie nth node from the end, and then we can shift the position of the previous node two places front.
We must be aware that if n value is the total length of the linked list, then it is the first node that we want to delete, and we can just shift the head to the next node.
Approach
- Use 2 pointers, slow, fast.
- We move the pointer fast until n > 0, so that we can get a gap of n elements between slow and fast.
- Move the fast pointer to the next pointer and again traverse until fast is null.
- This time, also move the slow pointer so that when fast is null, the slow pointer would reach the previous node of the targeted node.
- Now move the next of slow pointer to next of the targeted node.
Complexity
- Time complexity:
O(N) - as we are traversing the linked list only once, this is a one-pass solution.
- Space complexity:
O(1) as there is no extra space used.
Code
/**
* 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) {
if (head == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) {
// meaning deleting first number
return head.next;
}
fast = fast.next;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}
This content originally appeared on DEV Community and was authored by Rohith V
Rohith V | Sciencx (2025-03-29T08:15:42+00:00) Leetcode 19 : Remove nth Node from end of List. Retrieved from https://www.scien.cx/2025/03/29/leetcode-19-remove-nth-node-from-end-of-list/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.