Algorithm
Problem Name: 19. Remove Nth Node From End of List
Problem Link: https://leetcode.com/problems/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 <= 300 <= Node.val <= 1001 <= n <= sz
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *a, *b, *p = NULL;
a = b = head;
while (n-- > 0) { // b moves n steps first
b = b->next;
}
while (b) { // a, b move together, keeps a gap of n steps
p = a;
a = a->next;
b = b->next;
}
if (a == head) { // a is the one to be removed
head = a->next;
} else {
p->next = a->next;
}
free(a);
return head;
}
Input
head = [1,2,3,4,5], n = 2
Output
[1,2,3,5]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* slow(head), *fast(head);
while(n--) fast = fast->next;
if(!fast) return head->next;
while(fast->next) slow = slow->next, fast = fast->next;
slow->next = slow->next->next;
return head;
}
};
Input
head = [1], n = 1
Output
[]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode curr = head;
while (n-- > 0) {
curr = curr.next;
}
if (curr == null) {
return head.next;
}
ListNode slowNode = head;
while (curr.next != null) {
slowNode = slowNode.next;
curr = curr.next;
}
slowNode.next = slowNode.next.next;
return head;
}
}
Input
head = [1,2], n = 1
Output
[1]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const removeNthFromEnd = (head, n) => {
if (head.next === null) return null;
let ptrBeforeN = head;
let count = 1;
// While there are more elements
let el = head.next;
while (el !== null) {
if (count > n) ptrBeforeN = ptrBeforeN.next;
el = el.next;
count++;
}
if (count === n) return head.next;
ptrBeforeN.next = ptrBeforeN.next.next;
return head;
};
Input
head = [1,2,3,4,5], n = 2
Output
[1,2,3,5]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _019_RemoveNthNodeFromEndOfList
{
public ListNode RemoveNthFromEnd(ListNode head, int n)
{
if (head == null || n <= 0) { return null; }
ListNode fakeHead, node1, node2;
fakeHead = new ListNode(-1);
fakeHead.next = head;
node1 = node2 = fakeHead;
for (int i = 0; i < n; i++)
{
if (node1 == null) { return null; }
node1 = node1.next;
}
if (node1 != null)
{
while (node1.next != null)
{
node1 = node1.next;
node2 = node2.next;
}
node2.next = node2.next.next;
}
return fakeHead.next;
}
}
}
Input
head = [1,2], n = 1
Output
[1]