Swap Neighbor Pairs
MediumLinked List
Problem
A dance line is a singly linked list. On the whistle, partners swap places: the 1st and 2nd dancers trade, the 3rd and 4th trade, and so on. A dancer without a partner at the end stays put.
Given the head, swap every two adjacent nodes by relinking them (do not change any values) and return the new head.
Example 1
- Input:
- head = [1, 2, 3, 4, 5]
- Output:
- [2, 1, 4, 3, 5]
Pairs (1, 2) and (3, 4) swap; 5 has no partner.
Example 2
- Input:
- head = [8, 9]
- Output:
- [9, 8]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- 0 ≤ node.val ≤ 100
- Values must not be modified.
Hint
Show the first hint
Swapping two nodes affects three links: the one into the pair, the one between them and the one out of the pair.
Walkthrough
How to approach it
01Clarify before coding
- May I just swap the values? No, nodes must be relinked.
- What about an odd node at the end? It stays where it is.
- Is recursion fine? It works, but 10^4 levels is risky in Python; iterate.
02Brute force
Put all nodes in an array, swap array entries pairwise, then relink the array in order.
Cost: O(n) time and O(n) extra space for the array.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.