Swap Kth nodes from ends

Summary

Given a singly linked list, swap the kth node from the beginning and the kth node from the end. The problem is about manipulating a linked list to swap two nodes at specific positions.

Detailed Explanation

To solve this problem, we'll first find the kth node from the beginning of the linked list, then move to the end of the list and find the kth node from there. Once both nodes are found, we'll update their values by swapping them.

Here's a step-by-step breakdown:

Initialize two pointers: start and end. start will point to the beginning of the list, while end will move towards the end of the list.
Find the kth node from the beginning of the list using start. Move start k-1 steps forward.
Find the kth node from the end of the list using end. Move end to the kth node from the end.
Swap the values of the two nodes.

Time complexity: O(n), where n is the number of nodes in the linked list. We're moving through the list twice, so it's linear time complexity.

Space complexity: O(1), as we're not using any extra space.

Here's an ASCII art diagram to illustrate the process:

      +--------+  // Start
      |  Node  |
      +--------+
           ^
           |
           v
      +--------+  // End
      |  Node  |
      +--------+

Optimized Solutions

Java

public void swapKthNodesFromEnd(SinglyLinkedListNode node, int k) { SinglyLinkedListNode start = node; for (int i = 0; i < k - 1; i++) { start = start.next; } SinglyLinkedListNode end = node; for (int i = 0; i < node.length() - k; i++) { end = end.next; } int temp = start.data; start.data = end.data; end.data = temp; }