Swap Nodes in Pairs
Swap every two adjacent nodes in place using a dummy and a sliding triple.
2 min read
linked-list
Problem#
Swap every two adjacent nodes (not just values). For a trailing single node, leave it as is.
Examples#
[1,2,3,4]→[2,1,4,3][1,2,3]→[2,1,3]
Constraints#
0 <= n <= 100.
Approach#
Dummy head + a “before” pointer. Per iteration, take a = before->next, b = a->next; rewire before → b → a → b.next. Advance before to a (the new second of the pair).
Solution#
class Solution {public: ListNode* swapPairs(ListNode* head) { ListNode dummy(0, head); ListNode* before = &dummy; while (before->next && before->next->next) { ListNode *a = before->next, *b = a->next; a->next = b->next; b->next = a; before->next = b; before = a; } return dummy.next; }};func swapPairs(head *ListNode) *ListNode { dummy := &ListNode{Next: head} before := dummy for before.Next != nil && before.Next.Next != nil { a, b := before.Next, before.Next.Next a.Next = b.Next b.Next = a before.Next = b before = a } return dummy.Next}from typing import Optional
class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(0, head) before = dummy while before.next and before.next.next: a, b = before.next, before.next.next a.next = b.next b.next = a before.next = b before = a return dummy.nextvar swapPairs = function(head) { const dummy = new ListNode(0, head); let before = dummy; while (before.next && before.next.next) { const a = before.next, b = a.next; a.next = b.next; b.next = a; before.next = b; before = a; } return dummy.next;};class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0, head); ListNode before = dummy; while (before.next != null && before.next.next != null) { ListNode a = before.next, b = a.next; a.next = b.next; b.next = a; before.next = b; before = a; } return dummy.next; }}function swapPairs(head: ListNode | null): ListNode | null { const dummy: ListNode = new ListNode(0, head); let before: ListNode = dummy; while (before.next && before.next.next) { const a: ListNode = before.next; const b: ListNode = a.next; a.next = b.next; b.next = a; before.next = b; before = a; } return dummy.next;}Editorial#
A special case of reverse-in-k-group with k=2, but the explicit three-line rewire is cleaner and reads more directly. The dummy makes the head swap uniform.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#