Code Implementation

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        first = head
        for _ in range(k-1):
            first = first.next
        kth_from_start = first

        slow = head
        fast = head
        for _ in range(k):
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next
        kth_from_end = slow

        kth_from_start.val, kth_from_end.val = kth_from_end.val, kth_from_start.val
        return head
      

// Definition for singly-linked list.
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode* first = head;
        for (int i = 1; i < k; ++i) {
            first = first->next;
        }
        ListNode* kth_from_start = first;

        ListNode* slow = head;
        ListNode* fast = head;
        for (int i = 0; i < k; ++i) {
            fast = fast->next;
        }

        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* kth_from_end = slow;

        int temp = kth_from_start->val;
        kth_from_start->val = kth_from_end->val;
        kth_from_end->val = temp;

        return head;
    }
};
      

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

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode first = head;
        for (int i = 1; i < k; ++i) {
            first = first.next;
        }
        ListNode kthFromStart = first;

        ListNode slow = head;
        ListNode fast = head;
        for (int i = 0; i < k; ++i) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        ListNode kthFromEnd = slow;

        int temp = kthFromStart.val;
        kthFromStart.val = kthFromEnd.val;
        kthFromEnd.val = temp;

        return head;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var swapNodes = function(head, k) {
    let first = head;
    for (let i = 1; i < k; ++i) {
        first = first.next;
    }
    let kthFromStart = first;

    let slow = head;
    let fast = head;
    for (let i = 0; i < k; ++i) {
        fast = fast.next;
    }
    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }
    let kthFromEnd = slow;

    let temp = kthFromStart.val;
    kthFromStart.val = kthFromEnd.val;
    kthFromEnd.val = temp;

    return head;
};
      

Problem Description

Given the head of a singly linked list and an integer k, you are to swap the values of the kth node from the beginning and the kth node from the end of the list (the list is 1-indexed). You must return the head of the modified linked list.

• Each value in the list is unique, but you are only allowed to swap the values of the nodes, not the nodes themselves.
• You must not create new nodes or reuse elements.
• There is always at least one valid solution, and k is always valid (1 ≤ k ≤ list length).

Thought Process

The problem asks us to swap the values of two specific nodes in a singly linked list: the kth from the start and the kth from the end. The challenge is to find these nodes efficiently, especially since singly linked lists don't allow backward traversal.

A brute-force approach would be to traverse the list twice: once to find the total length, and then again to locate both nodes. However, we can optimize this by using two pointers to find the kth node from the end in a single traversal.

The key insight is that while the kth node from the start is straightforward to locate, the kth from the end can be found by advancing a second pointer k steps ahead and then moving both pointers until the lead pointer reaches the end.

Solution Approach

• Step 1: Use a pointer to traverse k-1 steps from the head to find the kth node from the start. Save this node as kth_from_start.
• Step 2: To find the kth node from the end, use two pointers: fast and slow. Move fast k steps ahead of slow.
• Step 3: Move both slow and fast forward together until fast reaches the end of the list. At this point, slow will be at the kth node from the end.
• Step 4: Swap the values of the nodes found in steps 1 and 3.
• Step 5: Return the head of the modified list.

This approach ensures that we only traverse the list at most twice, which is efficient for long lists.

Example Walkthrough

Let's consider the list 1 -> 2 -> 3 -> 4 -> 5 with k = 2:

1. The 2nd node from the start is 2.
2. To find the 2nd node from the end:
   • Start both slow and fast at head.
   • Move fast 2 steps ahead: fast is at node 3.
   • Move both pointers one step at a time:
     • slow at 2, fast at 4
     • slow at 3, fast at 5
     • slow at 4, fast at null (end)
   • Now, slow is at node 4, which is the 2nd from the end.
3. Swap the values of nodes 2 and 4. The list becomes 1 -> 4 -> 3 -> 2 -> 5.

Time and Space Complexity

• Brute-Force Approach:
  • First, traverse the entire list to find its length: O(N).
  • Then, traverse again to reach the kth node from the start and from the end: O(N).
  • Total time complexity: O(N).
  • Space complexity: O(1) (no extra space used).
• Optimized Approach (Two Pointers):
  • Traverse to the kth node from the start: O(k).
  • Use two pointers to find the kth node from the end in one traversal: O(N - k).
  • Total time complexity: O(N).
  • Space complexity: O(1).

Both approaches have linear time complexity, but the optimized one reduces the number of traversals and is more elegant.

Summary

The key to solving the Swapping Nodes in a Linked List problem is efficiently locating both the kth node from the start and the end. By using a two-pointer technique, we can do this in a single pass without extra space. The solution is elegant because it leverages the properties of singly linked lists and pointer manipulation, resulting in an O(N) time and O(1) space algorithm.