Medium

# 105. Swapping Nodes in a Linked List (Kth Position)

Objective: Given a Linked List and a number k, Swap the Kth Node from the front with the Kth Node from the End

Example:

```Input: -10-20-30-40-50-60-70

k=3
Output: -10-20-50-40-30-60-70

k=6
Output: -10-60-30-40-50-20-70

k=10
Output: INVALID NUMBER, No Swapping, k>length of list

k = 4
Output: Nodes are same from front and at the end, no swapping
```

Approach:

Before we proceed, let's establish a crucial understanding: the length of the linked list. We'll denote this as `Len'` for convenience.

First and foremost, we must address a crucial condition: if the value `k` exceeds the length of the list (`Len`), swapping cannot occur. It's essential to ensure that `k` falls within the boundaries of the list to proceed with the swapping process effectively.

Next, we encounter a scenario where the kth node from both the front and the end of the list are identical. In this situation, denoted by the condition (`2*k-1=Len`), swapping is unnecessary.

Assuming the above conditions are not met, we proceed with the swapping operation. Let's outline the steps involved:

#### Positioning the Left Pointer:

• Begin by moving a pointer, `left`, by `k` nodes within the list.
• Concurrently, keep track of the node prior to `left`, referred to as `left_prev`. This information is crucial for the subsequent swapping process.
• Set `left_prev` to null if `k` equals 1, denoting that `left` is the first node.

#### Positioning the Right Pointer:

• Move another pointer, `right`, by `Len-k+1` nodes within the list. This positions `right` at the kth node from the end.
• Similar to the `left` pointer, keep track of the node prior to `right`, termed `right_prev`, which is essential for the swapping mechanism.
• Set `right_prev` to null if `k` equals `Len`, signifying that `right` is the last node.

#### Swapping Nodes:

• If `left_prev` is not null, adjust it to point to `right`. This step ensures the integrity of the linked list structure.
• Similarly, if `right_prev` is not null, update it to point to `left`.
• Finally, swap the `next` pointers of `left` and `right.next` to complete the swapping process seamlessly.

A critical consideration arises at this juncture: updating the head of the list. If `k` equals 1, signifying that the first node is being swapped, set the head to `right`. Conversely, if `k` equals `Len`, indicating that the last node is being swapped, assign the head to `left`.

Output:

```Input: -10-20-30-40-50-60-70
Swapping Node number 3 from the Front and from the End
-10-20-50-40-30-60-70
```