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 :)
There are two approaches possible, in this post we will see the first one.
Approach 1: Two Pass
If you think a bit, nth
node from end is list_len - n + 1
th node from beginning.
So our algorithm is:
- Find the length of LinkedList β L
- Delete the (L - n + 1)th node from beginning.
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)
{
//- if LL is empty
if (!head)
return head;
//note: first pass : O(n)
//- getting length of LL
int cnt = 0;
ListNode *temp = head;
while (temp)
{
cnt++;
temp = temp->next;
}
//* Standard Procedure to delete (k+1)th node from beginning
//note: Required Node: (cnt - n +1)th node
//note: we have to go "cnt-n" times deep to stand at required node
int k = cnt - n;
ListNode *cur = head;
ListNode *prev = nullptr; //it will point one node preceding to cur
//note: second pass :O(n)
while (k > 0)
{
prev = cur;
cur = cur->next;
k--;
}
//- first node of the LL is to be deleted
if (!prev)
{
temp = cur;
cur = cur->next;
delete temp;
head = cur; //! cur is the new head
}
else
{
prev->next = cur->next;
delete cur;
}
return head;
}
Complexity Analysis
N is the length of LinkedList.
K is the postion of node from end.
Time Complexity: O(N)
Space Complexity: O(1)
We didn't use any extra space.
π‘ It turns out there's a better method to solve this question in single pass, we shall see that method in next post :)
Top comments (0)