Vultr DocsLatest Content

Swapping Nodes in a Linked List

Updated on 11 July, 2025
Swapping Nodes in a Linked List header image

Problem Statement

In the given task, you are presented with the head of a singly linked list and a number k. The objective is to modify the linked list by swapping the values of two specific nodes: the kth node from the beginning and the kth node from the end. It's important to note that the linked list uses a 1-based index. The function should then return the head of the modified linked list. This operation should be done within the constraints of the linked list's size and node value limits, ensuring that the swap is possible within those bounds.

Examples

Example 1

Input:

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

Output:

[1,4,3,2,5]

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]

Constraints

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 105
  • 0 <= Node.val <= 100

Approach and Intuition

  1. To tackle this problem, understanding the structure and traversal of a linked list is crucial. Here's a step-by-step approach to achieve the swap:

    • Calculate the length of the linked list while traversing it to find the kth node from the start.
    • Use the length to determine the position of the kth node from the end.
    • Once both nodes are identified, swap their values.

  2. Detailed Steps:

    • Traverse the linked list to determine its total length and identify the kth node from the start simultaneously.
    • Calculate the position of the kth node from the end using the formula: position from end = length - k + 1.
    • Loop through the list again to locate the kth node from the end.

  3. Swapping Values:

    • After identifying both nodes, swap their values. It's important to handle nodes carefully to avoid any pointer mismanagement that can corrupt the linked list.

  4. Edge Cases:

    • When k is such that the kth node from the beginning and the end are the same, the values should remain unchanged.
    • Properly handle scenarios when the linked list length equals 1 or when k equals 1 or the list length, as these might simplify or complicate the swap logic.

This method leverages direct node value swaps instead of rearranging the nodes themselves, which simplifies the task and avoids additional complexity related to node re-linking in a singly linked list.

Solutions

  • C++
cpp 
class Solution {
public:
    ListNode* swapKthNode(ListNode* head, int k) {
        int totalNodes = 0;
        ListNode* kthNode = nullptr;
        ListNode* lastKthNode = nullptr;
        ListNode* current = head;
        while (current) {
            totalNodes++;
            if(lastKthNode != NULL) {
                lastKthNode = lastKthNode->next;
            }
            if (totalNodes == k) {
                kthNode = current;
                lastKthNode = head;
            }
            current = current->next;
        }
        swap(kthNode->val, lastKthNode->val);
        return head;
    }
};

This solution implements a function to swap the k-th node from the beginning and the k-th node from the end in a given singly linked list. Written in C++, the function swapKthNode accepts a ListNode pointer (head) representing the head of the linked list and an integer k. The approach involves:

  • Iterating over the linked list to count the total number of nodes and to identify the k-th node from the beginning.
  • Once the k-th node is identified during the first traversal, initialize another pointer to start from the head and move it forward until it points to the k-th node from the end.
  • After identifying both nodes, swap their values without changing the actual node connections.
  • Finally, the function returns the modified list starting from head.

Using this method allows node values to be swapped efficiently without the need to modify the links between nodes, thus maintaining the structure of the original linked list.

  • Java
java 
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        int lengthOfList = 0;
        ListNode nodeAtK = null;
        ListNode nodeFromEnd = null;
        ListNode current = head;
        // Iterate over list to identify the nodes to be swapped
        while (current != null) {
            lengthOfList++;
            if (nodeFromEnd != null)
                nodeFromEnd = nodeFromEnd.next;
            // Set node at k
            if (lengthOfList == k) {
                nodeAtK = current;
                nodeFromEnd = head;
            }
            current = current.next;
        }
        // Swapping values at the kth and (length-k+1)th positions
        int tempVal = nodeAtK.val;
        nodeAtK.val = nodeFromEnd.val;
        nodeFromEnd.val = tempVal;
        return head;
    }
}

The Java code snippet implements a solution for swapping nodes in a singly linked list based on their positions. The task requires swapping the k-th node from the beginning with the k-th node from the end. Here's a breakdown of how the code accomplishes this:

  • Initialize variables to keep track of the total length of the list (lengthOfList), a reference to the node at position k (nodeAtK), and a reference to a node from the end (nodeFromEnd).

  • Traverse through the linked list using a while loop and simultaneously calculate its total length. During this traversal, determine the k-th node from the start and set up a pointer to start tracking the k-th node from the end as well, once the k-th node from the start is located.

  • After the first pass, nodeAtK points to the k-th node from the beginning, and nodeFromEnd points to the k-th node from the end, due to the second pointer starting its traversal k steps delayed.

  • Swap the values of nodeAtK and nodeFromEnd. This is done without having to rearrange any node links but rather by simply exchanging the values held by the nodes.

  • Return the modified list with the nodes' values swapped as required.

This approach is efficient because it only requires a single pass through the linked list to identify both the k-th node from the start and from the end, followed by a simple operation to swap their values. This ensures a time complexity of O(n) where n is the number of nodes in the linked list and a space complexity of O(1) since no additional structures are used.

Comments

No comments yet.