19. Remove Nth Node From End of List — LeetCode(Python)
I got you!
Problem:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
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]Constraints:
- The number of nodes in the list is
sz. 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Follow up: Could you do this in one pass?
Solution:
dummy = ListNode(0, head)
slow = dummy
fast = head
while n > 0:
fast = fast.next
n -= 1
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextExplanation —
If the length of the linked list is l, the nth node from end is the (l - n)th node from the head.
So we take a pointer to the nth position from the start.
This pointer is now (l - n) nodes away from the end.
Now, we shift a new pointer along with this old pointer, one node at a time, until this new pointer reaches the end of the linked list.
And since both pointers traverse equal number of nodes now, this would mean, we have reached the (l - n)th node from the start which is the one we want to delete.
To get our new pointer to reach the (l - n - 1)th node, we use a dummy node, and start our traversal from there.
Next, we delete the next node to our current new pointer.
Time Complexity —
Since we are traversing each element in the list at most twice, we can say that our algorithm runs in linear time.
Also, our algorithm requires a constant amount of extra space.
Thus, if n is the length of the list,
Time Complexity: O(n)
Space Complexity: O(1)
