Problem Statement in English

Given a linked list, swap every two adjacent nodes and return its head.

Approach

This is a classic linked list problem. You have to move the pointers around.

Solution in Python


# 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]:
        dummy = ListNode()
        dummy.next = head

        prev = dummy
        temp = head

        while temp and temp.next:
            next = temp.next

            prev.next = next
            temp.next = next.next
            next.next = temp

            prev = temp
            temp = temp.next

        return dummy.next

Complexity

  • Time: O(n)O(n)
    Since we iterate over the list once.

  • Space: O(1)O(1)
    Since we don’t use any extra space.

And we are done.