grid47 Exploring patterns and algorithms
Nov 5, 2024
5 min read
Solution to LeetCode 19: Remove Nth Node From End of List Problem
You are given the head of a singly linked list. Your task is to remove the nth node from the end of the list and return the updated list.
Problem
Approach
Steps
Complexity
Input: The input consists of a singly linked list and an integer n.
Example: head = [1, 2, 3, 4, 5], n = 2
Constraints:
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz
Output: The output is the updated list after removing the nth node from the end.
Example: [1, 2, 3, 5]
Constraints:
• The list will always have at least n nodes.
Goal: The goal is to remove the nth node from the end of the list by first calculating the size of the list and then locating the node to remove.
Steps:
• Calculate the length of the linked list.
• Determine the target node to remove (n-th node from the end).
• Traverse the list again to find the node just before the target node.
• Update the next pointer of the previous node to skip the target node.
Goal: The input will always be a valid linked list, and n will always be a valid number within the list size.
Steps:
• 1 <= sz <= 30
• 1 <= n <= sz
• The linked list has at least one node.
Assumptions:
• The list is non-empty and contains at least one node.
• Input: Input: head = [1, 2, 3, 4, 5], n = 2
• Explanation: The list is [1, 2, 3, 4, 5]. Removing the 2nd node from the end (node 4) results in [1, 2, 3, 5].
Approach: The approach involves first calculating the length of the list, then finding the target node and updating the list pointers to remove the desired node.
Observations:
• The key observation is that once we know the length of the list, we can easily identify the node to remove.
• First, count the total number of nodes, then subtract n to get the target node's index from the start of the list. Traverse the list again to remove that node.
Steps:
• Step 1: Traverse the list to count its size.
• Step 2: Calculate the target node index from the start (size - n).
• Step 3: Traverse the list again and stop at the node just before the target node.
• Step 4: Update the next pointer of the current node to skip the target node.
Empty Inputs:
• There will always be at least one node in the linked list.
Large Inputs:
• The list size is small, so performance with large inputs is not a concern.
Special Values:
• If the list contains only one node, removing it will leave the list empty.
Constraints:
• The list will always contain at least n nodes.
ListNode*removeNthFromEnd(ListNode* head, int n) {
ListNode* node = head;
int sz =0;
while(node) {
node = node->next;
sz++;
}
node = head;
int tgt = sz - n;
if(sz == n) return head->next;
for(int i =0; i < tgt-1; i++)
node = node->next;
if(node->next)
node->next = node->next->next;
return head;
}
1 : Function Declaration
ListNode*removeNthFromEnd(ListNode* head, int n) {
Declare the `removeNthFromEnd` function, which takes a pointer to the head of a linked list `head` and an integer `n` as input and returns a pointer to the head of the modified linked list.
2 : Variable Initialization
ListNode* node = head;
Initialize a pointer `node` to the head of the linked list.
3 : Variable Initialization
int sz =0;
Initialize a variable `sz` to store the size of the linked list.
4 : Loop Iteration
while(node) {
Start a loop to iterate through the linked list.
5 : Pointer Manipulation
node = node->next;
Move the `node` pointer to the next node in the linked list.
6 : Increment
sz++;
Increment the `sz` variable to count the number of nodes.
7 : Variable Initialization
node = head;
Reset the `node` pointer to the head of the linked list.
8 : Calculations
int tgt = sz - n;
Calculate the target index `tgt` of the node to be removed, which is the size of the list minus `n`.
9 : Conditional Return
if(sz == n) return head->next;
If `n` is equal to the size of the list, it means we need to remove the head node. Return the next node as the new head.
10 : Loop Iteration
for(int i =0; i < tgt-1; i++)
Iterate `tgt-1` times to reach the node before the node to be removed.
11 : Pointer Manipulation
node = node->next;
Move the `node` pointer to the next node in each iteration.
12 : Conditional Update
if(node->next)
Check if the next node exists.
13 : Pointer Manipulation
node->next = node->next->next;
If the next node exists, skip it by setting the `next` pointer of the current node to the node after the next node.
14 : Return Value
return head;
Return the head of the modified linked list.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In all cases, the solution involves two passes through the linked list, resulting in linear time complexity.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only need a few extra variables for tracking the list size and current node.
