LeetCode 24: Swap Nodes in Pairs

link

With four pointers (a, b, c, d) we can swap (b, c) in-place.

Since head might change, we introduce a dummy node to simplify edge-case handling.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        dummy = ListNode(next=head)
        a, b, c = dummy, head, head.next
        while c:
            d = c.next
            a.next = c
            b.next = d
            c.next = b

            if not d:
                break
            
            a, b, c = b, d, d.next

        return dummy.next

Leave a comment