In this series of posts, I will discuss coding questions on the LinkedList
Data structure.
The posts in this series will be organized in the following way,
- Question Link ❓
- Possible Explanation 📝
- Documented C++ Code 🧹
- Time and Space Complexity Analysis ⌛🌌
The Question
Given the head
of a linked list, remove the nth
node from the end of the list and return its head.
Constraints:
- The number of nodes in the list is
sz
. 1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
💡 Give yourself atleast 15-20 mins to figure out the solution :)
Approach 2: Single Pass
What do I mean by single pass here?
If you recall in the last post, we travelled the list two times:
LinkedList Questions: [Two Pass] Delete nth node from end
Kathan Vakharia ・ Jun 28 '21 ・ 2 min read
- To calculate the length of list.
- To delete the
L - n + 1
th node whereL
is the length of list.
That's the reason we called it two pass method.
But in this approach, we will travel the list only one time i.e. every node will be travelled exactly once.
Building Blocks
Before we begin our discussion, I would like you to be aware of few observations when traversing a linkedlist.
- If you travel
m
distance from the start, you'll end being on them + 1
th node. - If you append a dummy node(
start
) at the start of linkedlist, we can reach them
th node in original linkedlist inm
steps fromstart
. ( 1 step meanscur = cur→next
operation )
The Approach
📓 This approach might look a bit complicated but believe me, it is VERY important to understand it as this method forms the basis of many other questions( important ones ) on linkedlist.
Inorder to understand images, consider L=6( ListLength ) and n=3( postion of node from end that is to be deleted ).
The idea is still the same, we would want to delete the L - n + 1
th node from the beginning.
Here's what we will do,
1) Create a dummy node start
and make it' s next
equal to head
.
2) Initialize two pointers fast
and slow
equal to start
node i.e their next
is equal to head
.
3) Make fast
point to the n
th node in original linkedlist by peforming n
iterations( steps ).
🎯 Now hold on and think, how much steps will it take for fast
to reach the last node?
🎯 We are at the n
th node from start, so after L - n
steps we will reach the last node. [IMP]
4) Move fast
and slow
simultaneouly one step at a time untill fast
reaches the last node. This will ensure both pointers perform L - n
steps.
🎯 This will ensure, now slow
points to the L - n
th node. ( Point 2 of buldingblocks )
5) Delete the required node( slow → next
) using slow
pointer.
C++ Code
Definition of LinkedList
//Definition for singly-linked list.
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
Solution
ListNode *removeNthFromEnd(ListNode *head, int n)
{
//! list is never empty
//- initializing pointers
ListNode *start = new ListNode();
start->next = head;
ListNode *fast = start;
ListNode *slow = start;
//make fast point to the nth node
for (int i = 1; i <= n; i++)
{
fast = fast->next;
}
//move "slow" ahead untill "fast" points to the last node
//i.e point "slow" to one node preceding the required node
while (fast->next != nullptr)
{
fast = fast->next;
slow = slow->next;
}
//deleting the nth node from end or n-k+1th node from begin
ListNode *t = slow->next;
slow->next = slow->next->next;
delete t;
return start->next;
}
Complexity Analysis
L
is the length of linkedlist here
Time Complexity: O(L)
We have travelled the list exactly once.
Space Complexity: O(1)
We didn't use any extra space.
Top comments (0)