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 pointersfast 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:

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

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:

  1. Initialize two pointers fast and slow to reference the head of the linked list.
  2. 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.
  3. 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.
  4. Swap the values of nodes p and q by exchanging their val property.
  5. 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:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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.

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

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

    1fast: 2 (Second node)
    2slow: 1 (Head of the list)
  3. 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)
  4. At this point, we have:

    1p (kth from the beginning): Node with value 2
    2q (kth from the end): Node with value 4
  5. 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
  6. The modified linked list now looks like this:

    1Modified Linked List: 1 -> 4 -> 3 -> 2 -> 5
  7. 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.

Solution Implementation

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
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
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
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
Not Sure What to Study? Take the 2-min Quiz:

How does merge sort divide the problem into subproblems?

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 using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫