19. Remove Nth Node From End of List

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

solution

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

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

*708. Insert into a Sorted Circular Linked List

# 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)