Given a singly linked list, swap kth node from beginning with kth node from end. Swapping of data is not allowed, only pointers should be changed.
Let X be the kth node from beginning and Y be the kth node from end. Following are the interesting cases that must be handled.
1) Y is next to X
2) X is next to Y
3) X and Y are same
4) X and Y don’t exist (k is more than number of nodes in linked list)
Read full article from Swap Kth node from beginning with Kth node from end in a Linked List | GeeksforGeeks
Let X be the kth node from beginning and Y be the kth node from end. Following are the interesting cases that must be handled.
1) Y is next to X
2) X is next to Y
3) X and Y are same
4) X and Y don’t exist (k is more than number of nodes in linked list)
void
swapKth(
struct
node **head_ref,
int
k)
{
// Count nodes in linked list
int
n = countNodes(*head_ref);
// Check if k is valid
if
(n < k)
return
;
// If x (kth node from start) and y(kth node from end) are same
if
(2*k - 1 == n)
return
;
// Find the kth node from beginning of linked list. We also find
// previous of kth node because we need to update next pointer of
// the previous.
node *x = *head_ref;
node *x_prev = NULL;
for
(
int
i = 1; i < k; i++)
{
x_prev = x;
x = x->next;
}
// Similarly, find the kth node from end and its previous. kth node
// from end is (n-k+1)th node from beginning
node *y = *head_ref;
node *y_prev = NULL;
for
(
int
i = 1; i < n-k+1; i++)
{
y_prev = y;
y = y->next;
}
// If x_prev exists, then new next of it will be y. Consider the case
// when y->next is x, in this case, x_prev and y are same. So the statement
// "x_prev->next = y" creates a self loop. This self loop will be broken
// when we change y->next.
if
(x_prev)
x_prev->next = y;
// Same thing applies to y_prev
if
(y_prev)
y_prev->next = x;
// Swap next pointers of x and y. These statements also break self
// loop if x->next is y or y->next is x
node *temp = x->next;
x->next = y->next;
y->next = temp;
// Change head pointers when k is 1 or n
if
(k == 1)
*head_ref = y;
if
(k == n)
*head_ref = x;
}