Similar Problems
Similar Problems not available
Remove Nth Node From End Of List - Leetcode Solution
LeetCode: Remove Nth Node From End Of List Leetcode Solution
Difficulty: Medium
Topics: linked-list two-pointers
The problem "Remove Nth Node From End Of List" on LeetCode asks us to remove the n-th node from the end of a singly linked list and return the modified list. In other words, given a linked list and an integer n, we have to remove the node from the list that is n positions away from the end of the list.
The input to the problem is a linked list represented as a chain of nodes, where each node has two fields: a value field that contains the node's data, and a next field that contains a pointer to the next node in the list. The last node of the linked list has a next field that is NULL.
The output of the problem should be the modified linked list, where the n-th node from the end has been removed.
We can solve this problem using a two-pass algorithm, where in the first pass we count the total number of nodes in the list, and then in the second pass we remove the n-th node from the end of the list.
Here is the detailed solution using this algorithm:
- Initialize two pointers, current and temp, to the head of the linked list.
- Traverse the list using current pointer to count the number of nodes in the list. Let the count be N.
- Compute the position of the node to be removed as (N - n + 1), where n is the given input.
- If the position is 1, remove the head node and return the modified linked list.
- If the position is greater than 1, set the temp pointer to the node at position (position - 1).
- Set the next field of the node pointed to by temp to the node pointed to by the next field of temp.
- Return the modified linked list.
Here is the implementation of the above algorithm in Python:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
# Step 1: Initialize pointers current and temp to the head of the linked list
current = head
temp = head
# Step 2: Traverse the list to count the number of nodes in the list
count = 0
while current:
count += 1
current = current.next
# Step 3: Compute the position of the node to be removed
position = count - n + 1
# Step 4: If the position is 1, remove the head node and return the modified linked list
if position == 1:
return head.next
# Step 5: If the position is greater than 1, set the temp pointer to the node at position (position - 1)
for i in range(position - 2):
temp = temp.next
# Step 6: Set the next field of the node pointed to by temp to the node pointed to by the next field of temp
temp.next = temp.next.next
# Step 7: Return the modified linked list
return head
The time complexity of this solution is O(n), where n is the number of nodes in the linked list, since we do a two-pass traversal of the list. The space complexity is O(1), since we use a constant amount of extra memory.
Remove Nth Node From End Of List Solution Code
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9class Solution {
10public:
11 ListNode* removeNthFromEnd(ListNode* head, int n) {
12 // Base case
13 if (head == NULL) {
14 return NULL;
15 }
16
17 // Two pass algorithm
18 // 1. Calculate the length of the list
19 int length = 0;
20 ListNode* curr = head;
21 while (curr != NULL) {
22 length++;
23 curr = curr->next;
24 }
25
26 // 2. Remove the nth node from the end
27 int count = 0;
28 curr = head;
29 ListNode* prev = NULL;
30 while (count < length - n) {
31 prev = curr;
32 curr = curr->next;
33 count++;
34 }
35
36 // Remove the node
37 if (prev == NULL) {
38 // This is the case where we need to remove the head node
39 head = head->next;
40 } else {
41 prev->next = curr->next;
42 }
43
44 delete curr;
45
46 return head;
47 }
48};