What is the brute force approach and complexity for Swapping Nodes in a Linked List?

Copy to a vector, swap two indices, write the values back with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Swapping Nodes in a Linked List?

first = k-th from start; then fast from first and second from head until fast is last with optimal time complexity O(N) and space complexity O(1).

Swapping Nodes in a Linked List

Q: How do you identify the pattern for Swapping Nodes in a Linked List?

Look for key signals in the prompt: "k-th node from the end" indicates A position counted from the end → a gap between two pointers.; "k-th node from the start" indicates Walking there creates a pointer that is already k − 1 nodes ahead.; "swap the values" indicates No relinking. Find two nodes and swap two ints.; "1-indexed k" indicates k-th node is k − 1 steps from the head. The gap is k − 1, not k..

Medium·LeetCode #1721 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given the head of a linked list and a number k. Positions are counted from 1.

Swap the values of two nodes: the k-th node from the start and the k-th node from the end. Return the head of the list.

Input

The head of a linked list with n nodes, and an integer k with 1 ≤ k ≤ n.

Output

The head of the same list after the two values are swapped.

Example 1

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

Output: [1, 4, 3, 2, 5]

2nd from the start is 2, 2nd from the end is 4. Swap them.

Example 2

Input: head = [7, 9, 6, 6, 7, 8, 3, 0, 9, 5], k = 5

Output: [7, 9, 6, 6, 8, 7, 3, 0, 9, 5]

5th from the start is 7 (position 5), 5th from the end is 8 (position 6). Swap them.

Example 3

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

Output: [1, 2, 3, 4, 5]

In a list of odd length, the middle node is k-th from both ends, so it swaps with itself and nothing changes.

Constraints

• The list has n nodes, 1 ≤ k ≤ n ≤ 10^5
• 0 ≤ Node.val ≤ 100

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“k-th node from the end”

→ A position counted from the end → a gap between two pointers.

“k-th node from the start”

→ Walking there creates a pointer that is already k − 1 nodes ahead.

“swap the values”

→ No relinking. Find two nodes and swap two ints.

“1-indexed k”

→ k-th node is k − 1 steps from the head. The gap is k − 1, not k.

Approach Complexity Ladder

Brute Force — copy values into an arrayO(N)O(N)

Copy to a vector, swap two indices, write the values back

Better — count the length, then walk to both nodesO(N)O(1)

Count n; walk k − 1 steps for one node and n − k steps for the other

Optimal — one pass with a gap of k − 1O(N)O(1)

first = k-th from start; then fast from first and second from head until fast is last

Brute Force Intuition

Copy all values into a vector. In an array, the k-th from the start is index k − 1 and the k-th from the end is index n − k. Swap those two, then walk the list again and write the values back.

Recognition rule for this sub-pattern:

Give one pointer a head start (n steps, or the other list's length) so both reach the target together.

Remember this · Linked List — Fast & Slow

Trigger

Cycle detection, middle of list, "n-th from end", two lists meeting, repeating sequences.

Think

If one pointer moves faster or starts earlier, where will they meet?

Key question

What speed or gap makes the meeting point tell me the answer?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Fast & Slow translate into production architectures and low-level memory mechanics.

LLD Architecture