Swap Nodes in Pairs

MEDIUM

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

Example 1:

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

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

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

Approaches

Checkout 2 different approaches to solve Swap Nodes in Pairs. Click on different approaches to view the approach and algorithm in detail.

Recursive Approach

This approach solves the problem by defining a function that swaps the first two nodes of a list and then recursively calls itself on the rest of the list. The base case for the recursion is a list with zero or one node, which is returned as is.

Algorithm

Check for the base case: if the list is empty (head == null) or has only one node (head.next == null), return the head as no swap is possible.
Identify the first two nodes to be swapped: firstNode = head and secondNode = head.next.
The rest of the list, starting from secondNode.next, needs to be processed recursively. Call swapPairs(secondNode.next).
Link the firstNode to the result of the recursive call. This means firstNode.next will point to the head of the swapped sublist.
Perform the swap for the current pair: secondNode.next should point to firstNode.
Return secondNode, as it is the new head of this swapped pair.

The recursive solution elegantly mirrors the definition of the problem. The main idea is to handle the first pair of nodes and then delegate the swapping of the remaining pairs to a recursive call.

Let's consider the list 1 -> 2 -> 3 -> 4. The function swapPairs is called on the head (node 1).

It identifies the first pair (1, 2).
It knows that after swapping, node 1's next pointer should point to the result of swapping the rest of the list, which is 3 -> 4.
It makes a recursive call swapPairs(3). This call will return the head of the swapped sublist, which is 4 -> 3.
Now, it can complete the swap of the first pair. It sets 1.next to 4 and 2.next to 1.
Finally, it returns 2 as the new head of the entire list.

/**
 * 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) {
        // Base case: if the list has 0 or 1 node, no swaps needed.
        if (head == null || head.next == null) {
            return head;
        }

        // Nodes to be swapped
        ListNode firstNode = head;
        ListNode secondNode = head.next;

        // Recursively call for the list starting from the third node.
        // This will be the new next for the first node after swapping.
        firstNode.next = swapPairs(secondNode.next);

        // Swap the first two nodes by changing pointers
        secondNode.next = firstNode;

        // secondNode is the new head of the swapped pair
        return secondNode;
    }
}

Complexity Analysis

Time Complexity: O(N)Space Complexity: O(N)

Pros and Cons

Pros:

The code is concise and closely follows the recursive structure of the problem, which can make it easier to understand.
It naturally handles the head of the list without needing a special dummy node.

Cons:

The space complexity is O(N) due to the recursion call stack, which is less efficient than an iterative solution.
For extremely long linked lists, this approach could lead to a StackOverflowError (though not an issue with the problem's constraints).

Code Solutions

Checking out 5 solutions in different languages for Swap Nodes in Pairs. Click on different languages to view the code.

/** * 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 is null || head . next is null ) { return head ; } ListNode t = SwapPairs ( head . next . next ); ListNode p = head . next ; p . next = head ; head . next = t ; return p ; } }

Video Solution

Watch the video walkthrough for Swap Nodes in Pairs

Patterns:

Recursion

Data Structures:

Linked List

Companies:

Adobe |Amazon |Apple |Bloomberg |