Swapping Nodes in a Linked List - Practice Coding Problems

Swapping Nodes in a Linked List - Problem

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the k^th node from the beginning and the k^th node from the end (the list is 1-indexed).

Note: You need to swap the values, not the nodes themselves.

Input & Output

Example 1 — Basic Case

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

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

💡 Note: The 2nd node from beginning has value 2, the 2nd node from end has value 4. After swapping, the list becomes [1,4,3,2,5]

Example 2 — Middle Element

$ 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]

💡 Note: The 5th node from beginning has value 7, the 5th node from end has value 8. After swapping values, we get [7,9,6,6,8,7,3,0,9,5]

Example 3 — Same Node

$ Input: head = [1], k = 1

› Output: [1]

💡 Note: Only one node in the list, so the 1st from beginning and 1st from end is the same node. No change needed.

Constraints

The number of nodes in the list is n.
1 ≤ k ≤ n ≤ 10⁵
0 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [1,2,3,4,5] with k=2

Identify

Find 2nd from start (value 2) and 2nd from end (value 4)

Swap

Exchange values to get [1,4,3,2,5]

Key Takeaway

🎯 Key Insight: Use two pointers - when first pointer moves k steps ahead, moving both together finds the symmetric positions efficiently

Asked in

a Amazon 45 M Microsoft 32 f Facebook 28 G Google 25

The key insight is to use two pointers to find both target nodes in a single pass. The optimal approach uses the two-pointer technique where one pointer moves k steps ahead first, then both move together until the first reaches the end. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Three Pass	O(n)	O(1)	Find length first, then locate both nodes separately and swap their values
Two Pointers - One Pass	O(n)	O(1)	Use two pointers to find both target nodes in a single traversal

Brute Force - Three Pass — Algorithm Steps

Step 1: Traverse the entire list to count nodes
Step 2: Traverse again to find kth node from beginning
Step 3: Traverse again to find kth node from end
Step 4: Swap the values of both nodes

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Length

First traversal counts all nodes

Find Positions

Two more traversals find both target nodes

Swap Values

Exchange values between the two nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head, int k) {
    if (!head) return head;
    
    // First pass: count nodes
    int length = 0;
    struct ListNode* current = head;
    while (current) {
        length++;
        current = current->next;
    }
    
    // Second pass: find kth from beginning
    current = head;
    for (int i = 0; i < k - 1; i++) {
        current = current->next;
    }
    struct ListNode* firstNode = current;
    
    // Third pass: find kth from end
    current = head;
    for (int i = 0; i < length - k; i++) {
        current = current->next;
    }
    struct ListNode* secondNode = current;
    
    // Swap values
    int temp = firstNode->val;
    firstNode->val = secondNode->val;
    secondNode->val = temp;
    
    return head;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

void printList(struct ListNode* head) {
    printf("[");
    struct ListNode* current = head;
    int first = 1;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    }
    printf("]\n");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head, k);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three separate traversals of the list, each taking O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

67.5K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Three Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler