LeetCode 1721 - Swapping Nodes in a Linked List

LeetCode Problem 1721

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers

Solution

Problem Understanding

The problem provides a singly linked list and an integer k. The task is to swap the values of the kth node from the start with the kth node from the end of the list. The list is 1-indexed, meaning that the first node is position 1, not 0. The input head represents the start of the linked list, and the output should be the modified list after performing the swap.

In other words, if the linked list has n nodes, we need to swap the values of the nodes at positions k and n-k+1. The list nodes themselves remain in the same order; only their values change.

The constraints indicate that the linked list can be fairly large, up to 105 nodes, and node values are small integers between 0 and 100. This allows for O(n) solutions but discourages any solution requiring O(n²) time. We are guaranteed that k is always valid, so no need to check for out-of-range indices.

Important edge cases include a single-node list, k pointing to the first or last node, and the situation where the kth node from start and end are the same node (i.e., the middle node in an odd-length list), in which case no swap is needed.

Approaches

The brute-force approach is to first traverse the entire linked list and store all nodes in an array. Once we have array access, the kth node from the beginning is at index k-1 and the kth node from the end is at index n-k. We can then swap their values and reconstruct the list. This works because random access via an array allows O(1) swapping. However, this requires O(n) extra space to store the nodes, which is unnecessary.

The optimal approach leverages a two-pointer technique. First, iterate to the kth node from the start and remember it. Then use a second pointer to locate the kth node from the end by iterating to the end while maintaining a pointer first k steps behind, or by simply counting the total nodes and computing the target index. Swap the values in place without using extra space. This reduces space complexity to O(1) while keeping time complexity O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Convert list to array, swap values, rebuild list
Optimal	O(n)	O(1)	Two-pointer approach, swap values in place

Algorithm Walkthrough

1. Start with the head of the list and traverse k-1 steps to reach the kth node from the start. Store a reference to this node as first.
2. Initialize another pointer second at the head and a current pointer at the head.
3. Traverse the list with current. After reaching the end, second should point to the kth node from the end by using the total node count or the two-pointer technique.
4. Swap the values of first and second.
5. Return the head of the linked list.

Why it works: Swapping the values rather than the nodes themselves avoids complex pointer adjustments and ensures O(1) space. The two-pointer technique guarantees that second ends up exactly k nodes from the end when current reaches the list’s tail.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        first = head
        for _ in range(k - 1):
            first = first.next
        
        kth_from_start = first
        kth_from_end = head
        current = first
        
        while current.next:
            current = current.next
            kth_from_end = kth_from_end.next
        
        kth_from_start.val, kth_from_end.val = kth_from_end.val, kth_from_start.val
        return head

In this Python implementation, we first locate the kth node from the start. Then, by advancing current to the end while moving kth_from_end along, we land at the kth node from the end. Swapping is performed on the val attributes to avoid restructuring the list.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapNodes(head *ListNode, k int) *ListNode {
    first := head
    for i := 1; i < k; i++ {
        first = first.Next
    }
    
    kthFromStart := first
    kthFromEnd := head
    current := first
    
    for current.Next != nil {
        current = current.Next
        kthFromEnd = kthFromEnd.Next
    }
    
    kthFromStart.Val, kthFromEnd.Val = kthFromEnd.Val, kthFromStart.Val
    return head
}

In Go, the approach is identical. The main differences are syntax for loops and struct field access. The nil check replaces Python’s implicit None handling.

Worked Examples

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

Step	current	kth_from_start	kth_from_end	list
0	1	2	1	[1,2,3,4,5]
1	2	2	1	[1,2,3,4,5]
2	3	2	2	[1,2,3,4,5]
3	4	2	3	[1,4,3,2,5]
4	5	2	4	[1,4,3,2,5]

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

Step	current	kth_from_start	kth_from_end	list
0	7	7	7	[7,9,6,6,7,8,3,0,9,5]
1	9	7	9	[7,9,6,6,8,7,3,0,9,5]
...	...	...	...	...

After traversing, swapping 5th from start (7) and 5th from end (8) yields [7,9,6,6,8,7,3,0,9,5].

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single traversal to locate both nodes from start and end
Space	O(1)	Only pointers are used, no extra data structures

Since we only traverse the list once and use constant extra pointers, the solution is both time and space efficient.

Test Cases

# Example test cases
assert Solution().swapNodes(ListNode.from_list([1,2,3,4,5]), 2).to_list() == [1,4,3,2,5]  # swap 2nd and 4th
assert Solution().swapNodes(ListNode.from_list([7,9,6,6,7,8,3,0,9,5]), 5).to_list() == [7,9,6,6,8,7,3,0,9,5]  # swap 5th and 6th

# Edge cases
assert Solution().swapNodes(ListNode.from_list([1]), 1).to_list() == [1]  # single node
assert Solution().swapNodes(ListNode.from_list([1,2]), 1).to_list() == [2,1]  # swap first and last
assert Solution().swapNodes(ListNode.from_list([1,2,3]), 2).to_list() == [1,2,3]  # middle node, no change

Test	Why
Single node	Tests minimum input size
Two nodes, k=1	Tests swapping first and last nodes
Middle node, odd-length	Tests swap where nodes coincide

Edge Cases

Single-node list: Since the list has only one node, kth from start and end are identical. Swapping values changes nothing, which is correctly handled by the algorithm.

k pointing to first or last node: When k is 1 or equal to n, the swap affects the head or tail. The implementation correctly handles these by locating nodes with a simple pointer traversal.

Odd-length list with middle node: When the kth node from start and end are the same, swapping the values has no effect. The algorithm naturally handles this because the pointers will reference the same node, and swapping a value with itself is safe.

This approach covers all edge cases efficiently while maintaining optimal time and space complexity.