LeetCode 24 - Swap Nodes in Pairs - Python

 

Question:

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Answer:

When we first approach this problem, we might think about how we can swap two adjacent nodes in a linked list. One way to do this is to update the next pointers of the nodes so that they point to each other in reverse order.

Approach:

We start by creating a dummy node to serve as the previous node for the head node.

We then iterate through the linked list, swapping pairs of nodes by updating their next pointers.

We move the previous node pointer to the first node in the pair.

The new head of the list is returned as the next node of the dummy node.

Time complexity:

O(n)

The time complexity of this solution is linear because we need to iterate through all n nodes in the linked list.

Space complexity:

O(1)

The space complexity of this solution is constant because we only use a few extra variables to keep track of the previous and current nodes.

Code:

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while head and head.next:
            first_node = head
            second_node = head.next

            prev.next = second_node
            first_node.next = second_node.next
            second_node.next = first_node

            prev = first_node
            head = first_node.next
        return dummy.next