24. Swap Nodes in Pairs

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

Examples

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]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def swapPairs(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:
        # Nodes to be swapped
        first = head
        second = head.next
        
        # Swapping
        prev.next = second
        first.next = second.next
        second.next = first
        
        # Move pointers
        prev = first
        head = first.next
    
    return dummy.next

Java Solution


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (head != null && head.next != null) {
            // Nodes to be swapped
            ListNode first = head;
            ListNode second = head.next;
            
            // Swapping
            prev.next = second;
            first.next = second.next;
            second.next = first;
            
            // Move pointers
            prev = first;
            head = first.next;
        }
        
        return dummy.next;
    }
}

C++ Solution


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;
        
        while (head && head->next) {
            // Nodes to be swapped
            ListNode* first = head;
            ListNode* second = head->next;
            
            // Swapping
            prev->next = second;
            first->next = second->next;
            second->next = first;
            
            // Move pointers
            prev = first;
            head = first->next;
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

JavaScript Solution


/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    if (!head || !head.next) {
        return head;
    }
    
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;
    
    while (head && head.next) {
        // Nodes to be swapped
        const first = head;
        const second = head.next;
        
        // Swapping
        prev.next = second;
        first.next = second.next;
        second.next = first;
        
        // Move pointers
        prev = first;
        head = first.next;
    }
    
    return dummy.next;
};

C# Solution


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        while (head != null && head.next != null) {
            // Nodes to be swapped
            ListNode first = head;
            ListNode second = head.next;
            
            // Swapping
            prev.next = second;
            first.next = second.next;
            second.next = first;
            
            // Move pointers
            prev = first;
            head = first.next;
        }
        
        return dummy.next;
    }
}

Complexity Analysis

Solution Explanation

This solution uses an iterative approach to swap adjacent nodes. Here's how it works:

Key points: