Home » Interview Questions » LinkedList Interview Questions » Swap kth node from beginning with kth node from end

Swap kth node from beginning with kth node from end


()

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

READ  Find Nth Node

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions