Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes; only nodes themselves may be changed.
For example, given the linked list 1 -> 2 -> 3 -> 4, return 2 -> 1 -> 4 -> 3.
Write a function to solve this problem in Python.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def swapPairs(head):
dummy = ListNode(0)
dummy.next = head
prev_node = dummy
while head and head.next:
first_node = head
second_node = head.next
# Swapping
prev_node.next = second_node
first_node.next = second_node.next
second_node.next = first_node
# Move to the next pair
prev_node = first_node
head = first_node.next
return dummy.next
This solution initializes a dummy node to the head of the list, allowing us to handle special cases where the head needs to be swapped. It then iterates through the linked list, swapping every pair of nodes and updating their pointers accordingly. Finally, it returns the new head of the modified list.
The time complexity of this solution is O(n) where n is the number of nodes in the linked list, as we iterate through the list only once. The space complexity is O(1) as we only use a constant amount of extra space regardless of the size of the input.