Skip to main content

Leetcode 24: Swap Nodes in Pairs

 

1. Problem Statement (Simple Explanation):


You are given the head of a singly linked list.

You must swap every two adjacent nodes and return the new head.

  • You cannot modify the node values; you must change the links (i.e., rearrange nodes).

  • If the list has an odd number of nodes, the last node stays where it is.


2. Examples:


Example 1:

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

Pairs to swap:

  • (1, 2) → becomes (2, 1)

  • (3, 4) → becomes (4, 3)

Output: [2,1,4,3]


Example 2:

Input: head = []

Output: []


Example 3:

Input: head = [1]

Only one node → no swap.

Output: [1]


Example 4:

Input: head = [1,2,3]

Pairs:

  • (1, 2) → (2, 1)

  • 3 stays as is.

Output: [2,1,3]


3. Approach 1 – Iterative Pointer Manipulation (Dummy Node):


We’ll swap every pair of nodes by adjusting .next pointers.


Intuition:


Use a dummy node to simplify handling the head. Then, for each pair:

  • Suppose we have:

    • prev -> first -> second -> nextPairStart

  • We want to transform it to:

    • prev -> second -> first -> nextPairStart

Steps to swap:

  1. prev.next = second

  2. first.next = second.next (which is nextPairStart)

  3. second.next = first

Then move prev to first and continue with the next pair.


Algorithm (Step-by-Step):


  1. Create dummy = new ListNode(0) and set dummy.next = head.

  2. Set prev = dummy.

  3. While prev.next != null and prev.next.next != null:

    • first = prev.next

    • second = prev.next.next

    • Perform the swap:

      • prev.next = second

      • first.next = second.next

      • second.next = first

    • Move prev = first (since first is now the second node in the pair).

  4. Return dummy.next as the new head.


Pseudo-code (Iterative):



Complexity:


Let n be the length of the list:

  • Time: O(n) (each node is visited a constant number of times).

  • Space: O(1) extra.


4. Approach 2 – Recursive (Optional):


You can also solve this recursively:

  • Base cases:

    • head == null or head.next == null → return head.

  • Recursive step:

    • first = head

    • second = head.next

    • Recursively swap the rest starting from second.next:

      • first.next = swapPairs(second.next)

    • Then make second the new head of this pair:

      • second.next = first

    • Return second.

The recursive idea is elegant but uses recursion stack space O(n).


5. Java code:



6. C code:



7. C++ code:



8. Python code:


9. JavaScript code:


Comments

Post a Comment