This post is completed by 1 user

  • 0
 Add to List
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

Related Problems: