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

 

Translate ยป