Blind 75 — Programming & Technical Interview Questions — Explanation Series
The Problem:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Follow up: Could you do this in one pass?
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]The Constraints:
- The number of nodes in the list is
sz. 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
The Explanation:
To solve this problem I first went through an example on paper as if I was the computer: what info do I know, what don’t I, and what do I need to solve. The big thing missing is that you don’t know the size of the list but you have to remove the Nth node from the end. The only answer to this is you have to fully pass through the list to get the count. Now with this count you could pass through again until you reach the Nth-1 node and make its next the Nth+1 node. Minus a few corner cases this solves the problem, but how could you solve it in one pass? This requires a bit more complex solution. We know that the difference between the Nth to last node and the last is N positions. So you can get a “fast” node to the Nth position from the start. Then you can start a “slow” node and move each one to the next so there will always be N nodes between the two. This means that once the fast node reaches the end the slow node will be at the Nth from last position. Now you update just like before.
The Python Programming Solution:
This is almost word for word the explanation there is no fancy code here. Get the fast node to the Nth position. Then if the fast node is null we know that N == length of list so we just remove the first node. Then we advance both slow and fast until fast gets to the end and set the slow nodes next pointer to the next next pointer meaning we erased the Nth to last node.
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
fast = head
slow = head
# advance fast to nth position
for i in range(n):
fast = fast.next
if not fast:
return head.next
# then advance both fast and slow now they are nth postions apart
# when fast gets to None, slow will be just before the item to be deleted
while fast.next:
slow = slow.next
fast = fast.next
# delete the node
slow.next = slow.next.next
return head
Information:
Medium: medium.com/@nkwade
Website: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Email: nicholas@nkwade.dev
Twitter: twitter.com/nkwade_world
