MediumLinked ListRecursion

Swap Nodes in Pairs

1 approach, code in every language

You are given the head of a singly linked list. Rearrange the list by exchanging each pair of adjacent nodes, so the first node trades places with the second, the third with the fourth, and so on.

If the list contains an odd number of nodes, the final leftover node keeps its position. You are not allowed to change the values stored inside the nodes; the swap must be performed purely by relinking the next pointers. Return the head of the modified list.

Example 1

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

Output: [2,1,4,3]

The pair (1,2) becomes (2,1) and the pair (3,4) becomes (4,3).

Example 2

Input: head = [1,2,3]

Output: [2,1,3]

The first two nodes swap, while the lone trailing node 3 has no partner and stays where it is.

Constraints

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

Recursion

Swap the first two nodes, then recursively swap the rest of the list and attach the result.

Loading animation…

Intuition

Every pairwise swap on a linked list reduces to handling the first two nodes and trusting recursion for the remainder. If there are fewer than two nodes left, there is nothing to swap, so we return what we were given. Otherwise the second node becomes the new head of this segment. We point the original first node's next at whatever the recursive call produces for the rest of the list, then let the second node point back to the first. Returning the second node hands the correct new head up to the previous level of recursion.

Algorithm walkthrough

1Base case: if the list is empty or has a single node (head or head.next is null), return head unchanged because a pair cannot be formed.
2Capture the second node with second = head.next; it will become the head of this two-node segment after the swap.
3Recurse on second.next, which is the rest of the list beyond the current pair, and store the returned head in head.next.
4Set second.next = head so the second node now precedes the first, completing the local swap.
5Return second, the new head of this segment, so the caller can wire it into the list correctly.

Implementation

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        second = head.next
        head.next = self.swapPairs(second.next)
        second.next = head
        return second

Time

O(n)

Space

O(n)

n is the number of nodes. Each node is visited once, and the recursion stack grows to depth n/2 for the pending frames.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Swap Neighbouring Clips is our own problem on the technique behind Swap Nodes in Pairs: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free