# 19. Remove Nth Node From End of List

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

## solution

```python
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)

        i = 0
        slow = fast = dummy
        while i < n:
            fast = fast.next
            i += 1

        while fast.next is not None:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return dummy.next
```

时间复杂度：O(n)\
空间复杂度：O(1)

## follow up

[237. Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/description/)

```python
class Solution:
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next
```

[\*708. Insert into a Sorted Circular Linked List](https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/description/)

```python
# 1. 空list, 2. list中间位, 3. 排序list的edge

class Solution:
    def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
        node = Node(insertVal)
        if head is None:
            node.next = node
            return node

        prev = head
        cur = head.next
        while cur != head:
            if prev.val <= insertVal <= cur.val or (prev.val > cur.val and (insertVal >= prev.val or insertVal <= cur.val)):
                break
            prev = cur
            cur = cur.next
        prev.next = node
        node.next = cur
        return head
```

时间复杂度：O(n)\
空间复杂度：O(1)