Abstract / Summary

Given a linked list, pair up adjacent nodes and swap their positions throughout the list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (2+ million submissions).

Typical patterns to solve this problem:

• Linked List
• Recursion

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class that solves the classic “swap nodes in pairs” problem for a singly-linked list. The class contains two methods: two, which swaps a pair of adjacent nodes and returns the new left-most node of the swapped pair, and swapPairs, which repeatedly applies two to the entire list, building the final reordered list. The code is concise, leverages in-place pointer manipulation, and avoids auxiliary data structures.

Key Steps

Method two

def two(self, root):
    if not root:
        return None
    if not root.next:
        return root

    left  = root
    right = root.next

    left.next  = right.next
    right.next = left

    return right

The two method receives the head of a sub-list that potentially contains at least two nodes. It first checks for an empty sub-list and for a single-node sub-list, returning early in both cases. When two nodes are present, it binds left to the first node and right to the second. The core of the method reassigns left.next to skip over right and point to the node following the pair, then links right.next back to left. This effectively reverses the order of the two nodes while preserving the remainder of the list. The method finally returns right, which is now the left-most node of the swapped pair.

Method swapPairs

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return None

    result = current = self.two(head)
    while current and current.next and current.next.next:
        current.next.next = self.two(current.next.next)
        current = current.next.next

    return result

swapPairs begins by handling the empty list case. It then calls two on the original head, storing the returned node as both result (the eventual head of the transformed list) and current (the traversal pointer). The loop condition ensures that there are at least two more nodes ahead of current. Inside the loop, current.next.next-the node that follows the already-processed pair-is passed to two, and the returned node is linked as the next of current.next. The pointer current then advances two positions to the newly swapped pair, ready for the next iteration. When the loop exits, result points to the head of the fully swapped list, which is returned.

Edge Cases Handled

The code explicitly checks for a None head, returning None immediately, which covers the empty list scenario. In two, a check for a solitary node (root.next is falsy) returns the node unchanged, handling lists with an odd number of elements where the final node has no partner to swap with. The loop condition in swapPairs (current and current.next and current.next.next) guarantees that the body executes only when a complete pair is available, preventing attempts to access attributes of a None reference. Consequently, lists with a single node, two nodes, or any odd length are processed correctly without raising exceptions.

Performance Optimizations

The implementation performs swaps directly on the existing node objects, avoiding the allocation of new nodes or auxiliary containers. By reusing the original next pointers and only adjusting a constant number of references per pair, the algorithm runs in linear time relative to the number of nodes, with each node visited exactly once. The use of a single traversal pointer (current) eliminates the need for additional state variables or recursive calls, reducing call-stack overhead. Early returns for empty or single-node inputs prevent unnecessary work, ensuring that the function exits as soon as it can determine the result. The overall design keeps memory usage minimal by operating in place.

Imagine a long train made of many little colorful carriages all hooked together in a line. This code is like a very clever train conductor who wants to help pairs of carriages swap places with each other so they can see something different.

The part called two looks at just the first two carriages in a small group. It carefully unhooks them and flips their spots so the second one comes first and the first one goes second. It holds onto them while they swap so nobody gets lost.

The part called swapPairs looks at the whole long train. It starts at the very beginning and asks the conductor to swap the first group of two. Then it looks further down the track to find the next pair. It keeps moving along the train, jumping past the two carriages it just swapped to find the next pair waiting their turn. It repeats this process over and over, jumping from pair to pair, until it reaches the very end of the train where there are no more pairs left to flip around. Once the work is all finished, the train is ready to go with all the friends in their new spots.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java										TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		C#	Rust	JS		Ruby		Go	PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	AdelDaniel								Dart
	aylei						Rust
	begeekmyfriend				C
	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem									Ruby
	fengvyi	C++
	fsq	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost											Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	Shamik07								Dart
	shreymehul					C#
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vli02				C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666										Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Ruby, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fsq	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality