## In the given linked list, swap kth node from beginning with kth node from the end. We should not swap the values,we should swap pointers.

### Example

**Time complexity : O(n)**

## Algorithm

We should take care of 4 special conditions here, Let the nodes be M and N. M is kth node from beginning and N is kth node from end.

**a.** If M and N are same.

**b.** N is next of M

**c.** M is next of N

**d.** M and N doesn’t exist. (k > size of linked list)

**1.** We store the count of nodes in n.

**2.** If k > n, return without doing anything to linked list.

**3.** If 2k – 1 = n, M and N are same then, return without doing anything to linked list.

**4.** By traversing in the LL, we find kth node from beginning and ending and there previous nodes. (kth node from end is n-k+1th node from beginning)

**5.** If k == 1, we change the head pointer

**6.** We swap the next pointers of M and N and change there previous.

**7.** Do this only if previous exists and M previous not equal to N and vice versa.

**8.** In this conditions we need no swap previous of nodes.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct LLNode
{
int data;
struct LLNode* next;
};
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
struct LLNode* curr = new LLNode;
curr->data = dataToBeInserted;
curr->next = NULL;
if(*head == NULL)
*head=curr; //If this is first node make this as head of list
else
{
curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
*head=curr;
}
//O(1) constant time
}
//display linked list
void display(struct LLNode**node)
{
struct LLNode *temp= *node;
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<"->";
else
cout<<temp->data;
temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}
//function to swap nodes (k)
void swapKth(struct LLNode **head_ref, int k)
{
//N is count of nodes in linked list
struct LLNode *s = *head_ref;
int n = 0;
while(s != NULL)
{
n++;
s = s->next;
}
// if k > N return unchanged
if (n < k)
{
return;
}
// If M (kth node from begining) and N(kth node from end) are same
if (2*k - 1 == n)
{
return;
}
//store kth node from beginning in M
//Its previous in M_prev
struct LLNode *M = *head_ref;
struct LLNode *M_prev = NULL;
for (int i = 1; i < k; i++)
{
M_prev = M;
M = M->next;
}
//store kth node from the end in M
//kth node from end is N-k+1th node from beginning
//Its previous in M_prev
struct LLNode *N = *head_ref;
struct LLNode *N_prev = NULL;
for (int i = 1; i < n-k+1; i++)
{
N_prev = N;
N = N->next;
}
//considering cases M is next of N and N is next of M
if (M_prev)
{
M_prev->next = N;
}
if (N_prev)
{
N_prev->next = M;
}
//swap nexts of M and N
struct LLNode *temp = M->next;
M->next = N->next;
N->next = temp;
//for k = 1 and k = N
if (k == 1)
{
*head_ref = N;
}
if(k == n)
{
*head_ref = M;
}
}
// Driver program to test above functions
int main()
{
struct LLNode* head = NULL;//Initial list has no elements
insertAtBeginning(&head, 9);
insertAtBeginning(&head, 8);
insertAtBeginning(&head, 7);
insertAtBeginning(&head, 6);
insertAtBeginning(&head, 5);
insertAtBeginning(&head, 4);
insertAtBeginning(&head, 3);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 1);
int k;
cout<<"Input linked list: ";
display(&head);
cout<<"\nEnter k value: ";
cin>>k;
swapKth(&head,k);
cout<<"\nk: "<<k;
cout<<"\nOutput Linked List: ";
display(&head);
return 0;
}
```