algoadvance

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.)

Clarifying Questions

1. What is the structure of the linked list?
   • The linked list is typically implemented using nodes that contain a value and a pointer to the next node.
2. What should be the return value?
   • The function should return the head of the modified linked list.
3. Can the linked list be empty?
   • Yes, the function should handle the case where the linked list is empty.
4. What if the number of nodes in the list is odd?
   • If the number of nodes in the list is odd, the last node should remain in its original position since there is no pair to swap it with.

Strategy

1. Initialization:
   • Create a dummy node that helps simplify edge cases, especially when the list has fewer than two nodes.
   • Use three pointers: prev, first_node, and second_node to help in swapping the pairs.
2. Iteration:
   • Traverse through the linked list in increments of two nodes.
   • At each step, perform the swap by reassigning the pointers.
3. Swapping Logic:
   • Point the next of prev to second_node.
   • Reassign next of first_node to second_node.next.
   • Point the next of second_node to first_node.
   • Move prev two steps forward (to first_node).
   • Move first_node two steps forward (to the next pair’s first node).
4. Termination:
   • The loop terminates when there are fewer than two nodes left to process.
   • Return the next of the dummy node as the new head.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def swapPairs(head: ListNode) -> ListNode:
    # Create a dummy node to simplify edge cases.
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    
    while head and head.next:
        # Nodes to be swapped
        first_node = head
        second_node = head.next
        
        # Swapping
        prev.next = second_node
        first_node.next = second_node.next
        second_node.next = first_node
        
        # Reinitializing the pointers for next swap
        prev = first_node
        head = first_node.next
    
    # Return the new head node
    return dummy.next

Time Complexity

• Time Complexity: (O(n)), where (n) is the number of nodes in the linked list. The algorithm traverses the list once, swapping nodes in pairs.
• Space Complexity: (O(1)), as the algorithm uses a constant amount of extra space irrespective of the input size (excluding the space used to store the input linked list).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?