def deleteNode(node):
    # 题目保证 node 不是最后一个节点
    node.val = node.next.val      # 1. 把下一个节点的值复制过来
    node.next = node.next.next    # 2. 删除下一个节点（跳过它）

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)     # 哨兵节点：处理可能删除头节点的情况
        right = dummy
        for _ in range(n + 1):          # 右指针先走 n+1 步（走到第 n+1 个节点）
            right = right.next
        
        left = dummy                    # 左指针从 dummy 开始
        while right:                    # 左右指针一起走，直到右指针到末尾
            left = left.next
            right = right.next
        
        left.next = left.next.next      # 删除倒数第 n 个节点
        return dummy.next

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:                     # 特判空链表
            return head
        
        cur = head
        while cur.next:                   # 还有下一个节点就继续
            if cur.val == cur.next.val:    # 值相同，删除下一个节点
                cur.next = cur.next.next
            else:                         # 值不同，移动到下一个节点
                cur = cur.next
        return head

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)       # 哨兵节点：处理可能删除头节点的情况
        cur = dummy
        
        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:  # 发现重复
                val = cur.next.val                  # 记录待删除的值
                while cur.next and cur.next.val == val:
                    cur.next = cur.next.next         # 删除所有值等于 val 的节点
            else:
                cur = cur.next                       # 值不同，正常移动
        
        return dummy.next

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)     # 哨兵节点
        cur = dummy
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next  # 删除下一个节点
            else:
                cur = cur.next
        return dummy.next

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        st = set(nums)                     # 集合查找 O(1)
        dummy = cur = ListNode(next=head)
        while head:
            if head.val in st:
                cur.next = cur.next.next   # 在数组中，删除节点
                head = head.next
            else:
                cur = cur.next
                head = head.next
        return dummy.next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        head = self.reverseList(head)       # 反转后从左到右就是原链表的从右到左
        cur = head
        while cur.next:
            if cur.val > cur.next.val:      # 当前 ≤ 最大值，删除下一个
                cur.next = cur.next.next
            else:                           # 当前 > 最大值，保留并更新
                cur = cur.next
        return self.reverseList(head)       # 恢复反转

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        preA = list1
        for _ in range(a - 1):              # 1. 找到被删除段的前一个节点
            preA = preA.next
        
        postB = preA
        for _ in range(b - a + 2):           # 2. 找到被删除段的后一个节点
            postB = postB.next
        
        preA.next = list2                    # 3. 拼接 list2
        tail2 = list2
        while tail2.next:                    # 4. 找到 list2 的尾节点
            tail2 = tail2.next
        tail2.next = postB                    # 5. 尾节点连接 postB
        
        return list1