Description:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Examples:
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]Solution in Python:
To solve this problem of removing the nth node from the end of a linked list, we can use a two-pointer technique. This technique helps us to efficiently find and remove the nth node from the end in one pass through the list. Below is a step-by-step explanation and the corresponding Python code for this approach:
Steps:
- Create a dummy node: This dummy node helps in simplifying edge cases, such as when the head needs to be removed.
- Initialize two pointers: Both pointers start from the dummy node.
- Advance the first pointer: Move the first pointer n+1 steps ahead. This ensures that when the first pointer reaches the end of the list, the second pointer is at the (n+1)-th node from the end (i.e., just before the node to be removed).
- Move both pointers together: Move both pointers one step at a time until the first pointer reaches the end of the list.
- Remove the nth node: The second pointer will be pointing to the node just before the one to be removed. Adjust the pointers to skip the nth node.
- Return the new head: The head of the list is the next node of the dummy node.
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: ListNode, n: int) -> ListNode:
# Create a dummy node to simplify edge cases
dummy = ListNode(0)
dummy.next = head
# Initialize two pointers
first = dummy
second = dummy
# Move first pointer n+1 steps ahead
for _ in range(n + 1):
first = first.next
# Move both pointers until first reaches the end
while first:
first = first.next
second = second.next
# second is now pointing to the node before the one to be removed
second.next = second.next.next
# Return the new head of the list
return dummy.nextExplanation of the Code:
- Dummy Node: A dummy node is created and its
nextpointer is set to the head of the list. This helps handle edge cases where the head node itself needs to be removed. - Two Pointers:
firstandsecondpointers are initialized to point to the dummy node. - Advance
firstPointer: Thefirstpointer is movedn+1steps ahead. This creates a gap ofnnodes between thefirstandsecondpointers. - Move Both Pointers: Both pointers are moved one step at a time until the
firstpointer reaches the end of the list. - Skip the nth Node: The
secondpointer is now pointing to the node just before the node that needs to be removed. We adjust thenextpointer of thesecondpointer to skip the nth node. - Return New Head: Finally, we return the
nextnode of the dummy, which is the new head of the modified list.
This approach ensures that the problem is solved in a single pass through the list, providing an efficient solution.
Solution in Javascript:
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) {
// Create a dummy node to simplify edge cases
let dummy = new ListNode(0);
dummy.next = head;
// Initialize two pointers
let first = dummy;
let second = dummy;
// Move first pointer n+1 steps ahead
for (let i = 0; i <= n; i++) {
first = first.next;
}
// Move both pointers until first reaches the end
while (first !== null) {
first = first.next;
second = second.next;
}
// second is now pointing to the node before the one to be removed
second.next = second.next.next;
// Return the new head of the list
return dummy.next;
};Solution in Java:
Java
/**
* 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) {
// Create a dummy node that points to the head of the list
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize two pointers, both starting at the dummy node
ListNode first = dummy;
ListNode second = dummy;
// Move the first pointer n+1 steps ahead to maintain a gap of n between first and second
for (int i = 0; i <= n; i++) {
first = first.next;
}
// Move both pointers until the first pointer reaches the end of the list
while (first != null) {
first = first.next;
second = second.next;
}
// The second pointer is now at the node just before the one to be deleted
// Adjust the next pointer to skip the nth node from the end
second.next = second.next.next;
// Return the head of the modified list, which might be different if we removed the first node
return dummy.next;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
// Create a dummy node that points to the head of the list
ListNode dummy = new ListNode(0);
dummy.next = head;
// Initialize two pointers, both starting at the dummy node
ListNode first = dummy;
ListNode second = dummy;
// Move the first pointer n+1 steps ahead to maintain a gap of n between first and second
for (int i = 0; i <= n; i++) {
first = first.next;
}
// Move both pointers until the first pointer reaches the end of the list
while (first != null) {
first = first.next;
second = second.next;
}
// The second pointer is now at the node just before the one to be deleted
// Adjust the next pointer to skip the nth node from the end
second.next = second.next.next;
// Return the head of the modified list, which might be different if we removed the first node
return dummy.next;
}
}