Problem statement

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Solution

Two passes solution is straightforward. For one pass solution we use the idea of 2 iterators, let one of them start at the beginning, another at index n, then when the second one is finished, the first one will be on the right place.

Complexity

Time complexity is O(L), more precisely we make 2L-n steps, where L is length of list, space complexity is O(1). So it the end it is exactly the same as staightforward two passes solution. So, if you meet this problem in real interview, you can just explain two pass solution, and when interviewer say can you do better: explain him that another one pass solution in fact is exaclty the same time and space.

Code

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        P1, P2 = dummy, dummy
        for _ in range(n): P2 = P2.next
        
        while P2.next:
            P1 = P1.next
            P2 = P2.next
            
        P1.next = P1.next.next
        
        return dummy.next