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: , space:
.
# 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