Leetcode 19. Remove Nth Node From End of List

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

Linked list problem. Direct method requires 2 iterations, while using double pointers can save one.

Solution:

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

class Solution:
    # @param {ListNode} head
    # @param {integer} n
    # @return {ListNode}
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        p, q, i = dummy, dummy, n
        while i > 0:
            q = q.next
            i -= 1
        while q.next != None:
            p = p.next
            q = q.next
        # now we just need to remove the element behind p
        r = p.next
        p.next = r.next
        return dummy.next

Run Time: 48 ms