1721. Swapping Nodes in a Linked List

https://mech.run/docs/leetcode/1-500/swap_nodes_in_pairs

Python

• Time: O(N+K)
• Space: O(N)

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)

        # Find left position
        lpre, lcur = dummy, head
        for i in range(k-1):
            lpre = lpre.next
            lcur = lcur.next

        # Build the stack get ready to reverse travel
        stack = []
        cur = dummy
        while cur:
            stack.append(cur)
            cur = cur.next

        # Find right position from stack
        rcur = stack[-1]
        for i in range(k):
            rcur = stack.pop()
        rpre = stack.pop()

        # Swap the left and right position
        lpre.next, rpre.next = rcur, lcur
        lcur.next, rcur.next = rcur.next, lcur.next

        return dummy.next