Swap Nodes in Linked List

XXX. Swap Nodes in Linked List

Linked List

Two Pointers

Problem Statement:

You are given the head of a linked list, and an integer k. Swap the values of the kth node from the beginning with the kth node from the end (the list is 1-indexed).

Return the head of the modified linked list.

Approach:

1. Traverse the list to calculate its length and simultaneously locate the kth node from the beginning and the end.
2. During the traversal:
   • Increment the length for each node.
   • When reaching the kth node, store it as the "front node".
   • Start tracking the "end node" once the list length is greater than or equal to k.
3. Swap the values of the front node and the end node.

Java Implementation:

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public ListNode swapNodes(ListNode head, int k) {
    int listLength = 0;
    ListNode frontNode = null; // To store the k-th node from the start
    ListNode endNode = null;   // To store the k-th node from the end
    ListNode currentNode = head;
    
    // Traverse the list to find both the k-th nodes
    while (currentNode != null) {
        listLength++;
        if (endNode != null) 
            endNode = endNode.next;

        // Locate the k-th node from the start
        if (listLength == k) {
            frontNode = currentNode;
            endNode = head; // Start endNode tracking after k nodes
        }
        currentNode = currentNode.next;
    }
    
    // Swap values between frontNode and endNode
    int temp = frontNode.val;
    frontNode.val = endNode.val;
    endNode.val = temp;
    
    return head;
}
        

Key Insights:

• By traversing the list only once, you can determine the kth nodes from the beginning and the end simultaneously.
• This method avoids the need for a second pass through the list, improving efficiency.
• Swapping the values instead of the nodes ensures simplicity and avoids restructuring the list.

Complexity Analysis:

Time Complexity: O(n), where n is the length of the linked list.
Space Complexity: O(1), as no additional data structures are used.