< Back




24. Swap Nodes in Pairs

Kinda like reversing a linked list, except we reverse every two nodes. How do we accomplish this? As
always, maintaining a dummy node helps us start the process. The dummy node will point to the head
of the linked list, and be used to keep track of the pairs as we process them.

Next, we acquire a pointer to the first node and the second node. We point dummy node to the second
node as it's about to become the new head. We then point the first node to the second node's next
node. Then we point the second node to the first node. The two nodes have been swapped at this point.

Finally, we set the prev node to the first node, which is now techincally the second node in the
pair. We then set the head to the first node of the next pair. We repeat until head.next or head is
None. We finally return dummy.next which is the head of the linked list.

The solution is as follows:


  class Solution:
      def swapPairs(self, head: ListNode) -> ListNode:
          dummy = ListNode(-1)
          dummy.next = head

          prev_node = dummy

          while head and head.next:
              first_node = head
              second_node = head.next

              prev_node.next = second_node
              first_node.next = second_node.next
              second_node.next = first_node

              prev_node = first_node
              head = first_node.next

          return dummy.next


_ Time Complexity:

  O(n) - We traverse all nodes within the linked list.

_ Space Complexity:

  O(1) - We create one dummy node and a few pointers to traverse the linked list.