24. Swap Nodes in Pairs

Description of the Problem

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]

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Solution

Explanation

As illustrated below (in Haskell), swapping first two nodes and recursively call the function on remaining nodes again.

swapNodesInPair :: [a] -> [a]
swapNodesInPair [] = []
swapNodesInPair [x] = [x]
swapNodesInPair (x1:x2:xs) = x2:x1:(swapNodesInPair xs)

Code (Rust)

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
// 
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head{
            None => return None,

            // Move value as mutable
            Some(mut p) => {
                match p.next {
                    None => Some(p),
                    Some(mut q) => {
                        let rest = Self::swap_pairs(q.next);
                        p.next = rest;
                        q.next = Some(p);
                        return Some(q);
                    }
                }
            }
        }        
    }
}

Code (Java)

/**
 * 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){return null;}
        if (head.next == null) {return head;}

        ListNode temp = head.next.next;
        head.next.next = head;
        head = head.next;
        head.next.next = swapPairs(temp);
        return head;
    }
}

Complexity (n is the number of nodes in a linked list)

Time complexity:

• \( O(n) \)

Auxiliary Space:

• \( O(n) \)