We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Swap Nodes in Pairs

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires swapping nodes in pairs without altering their values.
  • A linked list can be manipulated by adjusting pointers rather than changing node values.
  • Special cases include handling lists with an odd number of nodes or zero nodes.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the linked list, as we traverse the list once. Space Complexity: O(1) - since we only use a constant amount of extra space for pointers.

Solution

We will use an iterative approach to swap the nodes in pairs. The algorithm involves:

  1. Initializing a dummy node to facilitate the swapping of the head.
  2. Using a pointer to traverse the list in pairs.
  3. Adjusting the pointers of the nodes to achieve the swap for each pair.
  4. Continuing this process until the end of the list is reached.

Code Solutions

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

def swapPairs(head: ListNode) -> ListNode:
    # Initialize a dummy node
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while prev.next and prev.next.next:
        # Identify the two nodes to swap
        first = prev.next
        second = prev.next.next
        
        # Perform the swap
        first.next = second.next
        second.next = first
        prev.next = second
        
        # Move the prev pointer forward
        prev = first
    
    return dummy.next
← Back to All Questions