19. Remove Nth Node From End of

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Approach 2: One pass algorithm

Algorithm

The above algorithm could be optimized to one pass. Instead of one pointer, we could use two pointers. The first pointer advances the list by <math><semantics><annotation encoding="application/x-tex">n+1</annotation></semantics></math>n+1 steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by <math><semantics><annotation encoding="application/x-tex">n</annotation></semantics></math>n nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the <math><semantics><annotation encoding="application/x-tex">n</annotation></semantics></math>nth node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node.

Figure. Remove the nth element from end of a list.

两个指针，相聚 n 个距离，快的到 tail, 慢的正好是删除节点前一个节点。

My one-pass solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        root = ListNode(0)
        root.next = head
        target_prev = root
        tail = root
        for i in range(n+1):
            tail = tail.next
        
        while tail is not None:
            target_prev = target_prev.next
            tail = tail.next
        
        if target_prev.next is not None:
            target_prev.next = target_prev.next.next
        else:
            target_prev.next = None
        return root.next