Home » Interview Questions » LinkedList Interview Questions » Swap nodes in the linked list

Swap nodes in the linked list


()

We are given a linked list and two key values, we need to swap these nodes.

Example

Time complexity : O(n)

Algorithm

We need to handle these cases,

a. x and/or y may not present in the linked list.

b. x or y may be last node.

c. x or y may be head node.

d. x and y may or may not be adjacent.

In the swap function,

1. If x and y are same, do nothing just return the same linked list.

2. Search for x and y, if either of x or y is not present, do nothing just return the same linked list.

3. If x is not head, make x_prev->next as y, else make y as new head.

4. If y is not head, make y_prev->next as x, else make x as new head.

5. Swap next pointers. (x->next, y->next)

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 x and y in linked list by
   changing links */
void swapNodes(struct LLNode **head_ref, int x, int y)
{
   //If x and y are same
   if (x == y)
   {
      return;
   }
   //search for x and store previous of x
   struct LLNode *x_prev = NULL, *x_curr = *head_ref;
   while (x_curr && x_curr->data != x)
   {
       x_prev = x_curr;
       x_curr = x_curr->next;
   }
 
   //search for y and store previous of y
   struct LLNode *y_prev = NULL, *y_curr = *head_ref;
   while (y_curr && y_curr->data != y)
   {
       y_prev = y_curr;
       y_curr = y_curr->next;
   }
   //x or y not present
   if (x_curr == NULL || y_curr == NULL)
   {
       return;
   }
   //If x is not head
   if (x_prev != NULL)
   {
       x_prev->next = y_curr;
   }
   //If x is head
   //make y as new head
   else
   { 
       *head_ref = y_curr;  
   }
   //If y is not head
   if (y_prev != NULL)
       y_prev->next = x_curr;
   //If y is head
   //make x as new head
   else
   {  
       *head_ref = x_curr;
   }
   // Swap next pointers
   struct LLNode *temp = y_curr->next;
   y_curr->next = x_curr->next;
   x_curr->next  = temp;
}
 
//Main function
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);           
    
    cout<<"Input linked list is: ";
    display(&head);
    int x = 2, y = 7;
    swapNodes(&head,x,y);

    cout<<"output LL after swapping "<<x<<" and "<<y<<" is: ";
    display(&head);

    return 0;
}

READ  Merge Two Sorted Lists Leetcode

 

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