1721. Swapping Nodes in a Linked List

Problem Description

In this problem, you are provided with the head of a singly linked list and an integer k. The goal is to return the modified linked list after swapping the values of two specific nodes: the kth node from the beginning and the kth node from the end. The linked list is indexed starting from 1, which means that the first node is considered the 1st node from both the beginning and the end in the case of a single-node list. Note that it's not the nodes themselves that are being swapped, but rather their values.

Intuition

To solve this problem, we think about how we can access the kth node from the beginning and the end of a singly linked list. A singly linked list does not support random access in constant time; meaning we can't directly access an element based on its position without traversing the list.

Given we only need to swap the values and not the nodes themselves, a two-pointer approach is perfect. The first step is to locate the kth node from the beginning which can be done by traversing k-1 nodes from the head. We use a pointer p to keep track of this node.

Finding the kth node from the end is trickier because we don't know the length of the linked list beforehand. However, by using two pointers – fast and slow – and initially set both at the head, we can move fast k-1 steps ahead so that it points to the kth node. Then, we move both fast and slow at the same pace. When fast reaches the last node of the list, slow will be pointing at the kth node from the end. We use another pointer q to mark this node.

Once we have located both nodes to be swapped, p and q, we simply exchange their values and return the (modified) head of the linked list as the result.

Learn more about Linked List and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Solution Approach

The implementation of the solution follows a two-pointer approach that is commonly used when dealing with linked list problems. The algorithm is simple yet powerful and can be broken down into the following steps:

Initialize two pointers fast and slow to reference the head of the linked list.
Move the fast pointer k-1 steps ahead. After this loop, fast will be pointing to the kth node from the beginning of the list. We use pointer p to mark this node.
Once the fast pointer is in position, we start moving both fast and slow pointers one step at a time until fast is pointing to the last node of the linked list. Now, the slow pointer will be at the kth node from the end of the list. We use another pointer q to mark this node.
Swap the values of nodes p and q by exchanging their val property.
Finally, return the modified linked list's head.

This is a classical algorithm that does not require additional data structures for its execution and fully utilizes the linked list's sequential access nature. It's efficient because it only requires a single pass to find both the kth node from the beginning and the kth node from the end, resulting in O(n) time complexity, where n is the number of nodes in the linked list.

The only tricky part that needs careful consideration is handling edge cases, such as k being 1 (swapping the first and last elements), k being equal to half the list's length (in the case of an even number of nodes), or the list having k or fewer nodes. However, since the problem only asks to swap values, the provided solution handles all these cases without any additional checks.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider a linked list and an integer k:

1Linked List: 1 -> 2 -> 3 -> 4 -> 5
2k: 2

Our task is to swap the 2nd node from the beginning with the 2nd node from the end.

Initialize two pointers fast and slow to reference the head of the linked list.

Move the fast pointer k-1 steps ahead. So, after this step:

1fast: 2 (Second node)
2slow: 1 (Head of the list)

Start moving both fast and slow one step at a time until fast points to the last node:

1Step 1:
2fast: 3
3slow: 2
4
5Step 2:
6fast: 4
7slow: 3
8
9Step 3:
10fast: 5 (Last node)
11slow: 4 (This becomes our `k`th node from the end)

At this point, we have:

1p (kth from the beginning): Node with value 2
2q (kth from the end): Node with value 4

Swap the values of nodes p and q:

1Node `p` value before swap: 2
2Node `q` value before swap: 4
3
4Swap their values.
5
6Node `p` value after swap: 4
7Node `q` value after swap: 2

The modified linked list now looks like this:

1Modified Linked List: 1 -> 4 -> 3 -> 2 -> 5

Return the head of the modified linked list, which points to the node with value 1.

This example illustrates the power of the two-pointer approach where pointer manipulation allows us to swap the kth nodes' values from the start and end of a singly linked list in O(n) time complexity without any additional space required.

Not Sure What to Study? Take the 2-min Quiz：

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Python Solution

1class ListNode:
2    def __init__(self, value=0, next_node=None):
3        self.value = value
4        self.next_node = next_node
5
6class Solution:
7    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
8        # Initialize two pointers that will start at the head of the list.
9        fast_pointer = slow_pointer = head
10      
11        # Move the fast pointer k-1 steps ahead, pointing to the kth node from the beginning.
12        for _ in range(k - 1):
13            fast_pointer = fast_pointer.next_node
14      
15        # Store the kth node from the beginning in a temporary variable 'first_k_node'.
16        first_k_node = fast_pointer
17      
18        # Move both pointers until the fast pointer reaches the end.
19        # At that point, slow pointer will point to the kth node from the end.
20        while fast_pointer.next_node:
21            fast_pointer = fast_pointer.next_node
22            slow_pointer = slow_pointer.next_node
23      
24        # Store the kth node from the end in a temporary variable 'second_k_node'.
25        second_k_node = slow_pointer
26      
27        # Swap the values of the kth node from the beginning and the kth node from the end.
28        first_k_node.value, second_k_node.value = second_k_node.value, first_k_node.value
29      
30        # Return the modified linked list head.
31        return head
32

Java Solution

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode() {}
7 *     ListNode(int val) { this.val = val; }
8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9 * }
10 */
11
12class Solution {
13    public ListNode swapNodes(ListNode head, int k) {
14        // Fast pointer that will be used to locate the kth node from the beginning
15        ListNode kthFromStart = head;
16      
17        // Move the kthFromStart pointer to the kth node
18        while (--k > 0) {
19            kthFromStart = kthFromStart.next;
20        }
21      
22        // This pointer will eventually point to the kth node from the end
23        ListNode kthFromEnd = head;
24      
25        // Fast pointer that will be used to reach the end of the list
26        ListNode current = kthFromStart;
27      
28        // Move the current pointer to the end, maintaining the gap between
29        // kthFromEnd and current, so that when current reaches the end,
30        // kthFromEnd is at the kth node from the end
31        while (current.next != null) {
32            current = current.next;
33            kthFromEnd = kthFromEnd.next;
34        }
35      
36        // Swap the values of the kth node from the start and end
37        int tempValue = kthFromStart.val;
38        kthFromStart.val = kthFromEnd.val;
39        kthFromEnd.val = tempValue;
40      
41        // Return the modified list
42        return head;
43    }
44}
45

C++ Solution

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* swapNodes(ListNode* head, int k) {
14        // Initialize a pointer to move k nodes into the list
15        ListNode* fast = head;
16        while (--k) { // Move the fast pointer k-1 times
17            fast = fast->next;
18        }
19        // At this point, fast points to the kth node from the beginning
20
21        // Initialize two pointers to find the kth node from the end
22        ListNode* slow = head; // This will point to the kth node from the end
23        ListNode* firstNode = fast; // Keep a reference to the kth node from the beginning
24
25        // Move both pointers until the fast pointer reaches the end of the list
26        while (fast->next) {
27            fast = fast->next;
28            slow = slow->next;
29        }
30        // Now, slow points to the kth node from the end
31
32        ListNode* secondNode = slow; // Keep reference to the kth node from the end
33
34        // Swap the values of the kth nodes from the beginning and end
35        std::swap(firstNode->val, secondNode->val);
36
37        // Return the head of the modified list
38        return head;
39    }
40};
41

Typescript Solution

1// Function to swap the kth node from the beginning with the kth node from the end in a singly-linked list
2function swapNodes(head: ListNode | null, k: number): ListNode | null {
3    // Initialize two pointers, both starting at the head of the list
4    let fast: ListNode | null = head;
5    let slow: ListNode | null = head;
6
7    // Move the 'fast' pointer to the kth node
8    while (--k) {
9        fast = fast ? fast.next : null;
10    }
11
12    // 'starting' points to the kth node from the beginning
13    // This node will later be swapped
14    let starting = fast;
15
16    // Move both 'fast' and 'slow' until 'fast' reaches the end of the list
17    // 'slow' will then point to the kth node from the end
18    while (fast && fast.next) {
19        fast = fast.next;
20        slow = slow ? slow.next : null;
21    }
22
23    // 'ending' points to the kth node from the end
24    let ending = slow;
25
26    // If both nodes to swap have been found, swap their values
27    if (starting && ending) {
28        let temp = starting.val;
29        starting.val = ending.val;
30        ending.val = temp;
31    }
32
33    // Return the head of the modified list
34    return head;
35}
36

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Time and Space Complexity

The time complexity of the provided code snippet is O(n), where n is the length of the linked list. This is because the code iterates over the list twice: once to find the k-th node from the beginning, and once more to find the k-th node from the end while simultaneously finding the end of the list.

The space complexity is O(1) since only a constant amount of additional space is used, regardless of the input size. No extra data structures are created that depend on the size of the list; only a fixed number of pointers (fast, slow, and p) are used.

Learn more about how to find time and space complexity quickly.

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1721. Swapping Nodes in a Linked List

Problem Description

Intuition

Solution Approach

Example Walkthrough

Python Solution

Java Solution

C++ Solution

Typescript Solution

Time and Space Complexity

Recommended Readings