Abstract / Summary

Given the head of a linked list and positions k and m swap the nodes from position k to m inclusive in place.

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 69% (600k+ submissions).

Typical patterns to solve this problem:

• Linked List
• Two Pointers

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 method that receives the head of a singly-linked list and an integer k. Its purpose is to exchange the values of the k-th node from the start with the k-th node from the end, then return the (unchanged) head reference. The algorithm proceeds in three conceptual phases: measuring the list length, locating the two target nodes, and performing an in-place value swap.

Length Computation

The first loop walks the list once, incrementing a counter until the end is reached. This establishes the total number of nodes, stored in size.

size = 0
scan = head
while scan:
    size += 1
    scan = scan.next

By using a simple while-loop that follows the next pointers, the code avoids any auxiliary data structures and keeps the memory footprint minimal.

Locating the Target Nodes

After the length is known, a second traversal iterates from the head while maintaining a 1-based index i. When i matches k, the current node is saved as one. When i matches size - k + 1, the current node is saved as two. The loop contains early-exit checks: as soon as both references have been assigned, the traversal stops, preventing unnecessary iteration over the remainder of the list.

one = None
two = None
scan = head
for i in range(1, size + 1):
    if i == k:
        one = scan
        if two:
            break
    if i == size - k + 1:
        two = scan
        if one:
            break
    scan = scan.next

The use of a single for loop with early termination means that, in the best case, the algorithm finishes after visiting only the portion of the list required to locate both nodes. This reduces the number of pointer dereferences compared with a naïve approach that would always walk the entire list twice.

Value Swapping

Once the two nodes are identified, their val fields are exchanged directly. No structural changes to the list are performed, which eliminates the need for re-linking pointers and avoids the risk of breaking list integrity.

one.val, two.val = two.val, one.val
return head

Swapping values rather than nodes is a deliberate optimization: it requires only a constant amount of work regardless of list size and sidesteps the overhead of updating multiple next references.

Edge-Case Handling

The algorithm gracefully handles several boundary conditions:

• When k refers to the first node (k == 1), one is set during the first iteration, and two is later found at the position size. The early-exit logic still applies once both references are known.
• When k refers to the last node (k == size), the symmetric situation occurs: one is discovered at the final iteration, while two is captured at the first iteration.
• When the list contains a single element (size == 1) and k == 1, both one and two point to the same node. The swap operation effectively leaves the list unchanged, which is the correct behavior.
• When k points to the middle of an odd-length list, the two target positions coincide (k == size - k + 1). In this case one and two become the same node, and swapping its value with itself is a no-op, preserving correctness without extra checks.
• If k is larger than the list length, the loop never satisfies the equality conditions, leaving one and two as None. However, the problem constraints guarantee a valid k, so the code assumes the indices will be found.

Performance Optimizations

Two notable optimizations are embedded in the design:

1. Early Termination in the Second Traversal - By checking whether both target nodes have been located after each assignment, the loop can break immediately, avoiding unnecessary passes over the tail of the list. This reduces the total number of pointer moves, especially when k is near the beginning or end.

2. Value-Based Swap Instead of Node Re-linking - Exchanging the val fields sidesteps the need to manipulate next pointers. This choice eliminates the risk of dangling references and keeps the operation confined to a constant-time assignment, regardless of list size.

Together, these choices ensure that the method runs with a minimal number of traversals and constant extra space, delivering efficient behavior for lists of any length within the problem’s constraints.

Imagine a train made of many toy cars linked together in a row. Each car has a little box inside with a number written on it.

First, the code goes from the front of the train to the back to count exactly how many cars there are. It needs to know the total length so it can find the right ones later.

Next, the code looks for two specific cars to swap. One car is the one at the position k, counting from the front. The other car is at the same position but counting from the far back of the train. It marches down the line of cars, one by one, watching for these two spots. When it reaches the first special car, it remembers it. When it reaches the second special car, it remembers that one too.

Finally, the code carefully takes the number out of the box in the first special car and the number in the box in the second special car. It puts the first number into the second car and the second number into the first car. It is just like swapping two secret notes. The train stays in the same order, but the two chosen cars have traded their secret numbers.

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	Python	Java	C++					TS
	WalkCCC	Python	Java	C++
	leetcode.ca	Python	Java	C++		C#		Go	TS
	Progiez	Python	Java	C++
github	black-shadows			C++
	chandansgowda	Python
	charles-wangkai		Java
	Dijkstra-Edu		Java
	everthis				JS
	fartem						Ruby
	fpdjsns			C++
	fsq			C++
	halfrost							Go
	JoshCrozier				JS
	lkwq007	Python
	shreymehul					C#
	suxrobGM					C#
	trung-hn	Python
	varunu28		Java
	vthwang		Java
	YuriSpiridonov	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
Dijkstra-Edu	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
YuriSpiridonov	Python

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