## 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; }