Remove Nth Node from End of List
- 2 min read
- LC-Medium
- Linked List
3 years ago
Solution
- Similar to Remove Kth Node From End that's from AlgoExpert
- Naive Solution is where you traverse the entire list, find the size, and the subtract to get which node you want to remove.
- Then you traverse the list again, now removing the link
- Optimal solution (although it's basically the same time complexity) is the following:
- Have slow and fast pointers. Slow is initially before the head (through use of a dummy, this negates the need for a prev variable)
- Move the fast pointer n times.
- Now, move slow and fast pointer at the same rate until the fast pointer reaches null.
- The node at slow.next is the node you want to remove. So just reset the link
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
Optimal Solution
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
slow = dummy = ListNode(0, head)
fast = head
while n:
fast = fast.next
n -= 1
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
Naive Solution
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# Find size of list
size = 0
cur = head
while cur:
size += 1
cur = cur.next
# If n = 1 and there's only one node in the list, return None
if n == size == 1:
return None
end = size - n
# If node to remove is the first node, return head.next
if end == 0:
return head.next
# Else, iterate through list and remove appropriate node.
i = 0
cur = head
while cur:
i += 1
if i == end:
cur.next = cur.next.next
return head
cur = cur.next