Move first node a middle of given linked list

Suppose following data [1, 2, 3, 4, 5, 6, 7, 8] are inserted on linked list.

Try it yourself

Following process to move first node at middle of linked list.

1) Use two pointer temp and helper. temp pointer and helper pointer are pointing to first node of linked list.

2) First find middle node of linked list.

3) move root pointer to second node of linked list.

root=root->next;

4) helper=temp->next;

First node of linked list that (next pointer) value are pointed to middle node of next node pointer.

5) temp->next=helper;

And finally middle node pointed to next node of this helper pointer.

Algorithm:

Time complexity of this algorithm O(n).

Code Execution:

Note that not given all step of execution process here.View How to insert linked list element, how to print and so on.

Try it yourself

c program to move first node at middle of linked list.

  /*
Help of this program we are learning how to move last 
Node at first position of given linked list.
*/

/*include header file*/
#include<stdio.h>
#include<stdlib.h>


/*Structure of linked list*/
struct Node{

  int data;// linked list data 
  struct Node*next;// pointer field
  
};

/* Function declaration section here */
void insert_data(struct Node**,int);
void show_data(struct Node*);
void remove_node(struct Node**);
void move_node(struct Node**);
/*Help of this function create new linked list node. 
And there are inserted this element on end position of given linked list*/
void insert_data(struct Node**root,int value){

  /* create new memory block using malloc function. */
  struct Node*temp=NULL,*new_node=(struct Node*)malloc(sizeof(struct Node));
  
  /* check new create memory are allocate or not. */
  if(new_node)
  {   

      /*Assign data and next pointer value to newly created node.*/
    new_node->data=value;
    new_node->next=NULL;

    if(*root==NULL){
      /*When linked list are empty. Insert first node*/
      *root=new_node;
    }
    else{
      /*When linked list are not empty*/

      /*linked list first node address assign on temp pointer*/
      temp=*root;
      
      /*This will loop find last node of exist linked list*/
      while(temp->next){
        /*move temp pointer on next memory block*/
        temp=temp->next;  
      }
      
      /*assign this newly created node on end of list*/
      temp->next=new_node;
      
    }         
  }
  else
  {
    /* When malloc function not create memory block then. */
    printf("\n Memory overflow please try again..!");
  }
}


/* Help of this function showing all element of single linked list */
void show_data(struct Node*temp){
  if(temp==NULL){
    /*linked list are empty*/
    printf("Empty linked List\n");
  }
  else
  {
    /*When linked list are not empty*/
    printf("linked list :");
    while(temp)
    {
      /*print linked list data*/
      printf("%d  ",temp->data);

      /*move next memory block*/
      temp=temp->next;
    }
    
  }
}
/*Help of this function removing all linked list element.*/
void remove_node(struct Node**root){

  if(*root){

    struct Node*temp=*root;
    
    while(temp){

      /*Moving root pointer to on next memory block.*/
      *root=temp->next;

      /*before removing that linked node assign
       next pointer value are null.*/
      temp->next=NULL;
      
      /*Free linked list node element*/
      free(temp);
      
      temp=*root;
    }
    printf("\n\n Free nodes of linked linked \n");
  }
  else{
    /* When linked list is empty */
    printf("\n linked list is empty \n");
  }
  
}
/*Move first node at middle of linked list*/
void move_node(struct Node**root){


  if(*root==NULL){
    /*If empty linked list*/
    printf("\n Linked list are empty");
  }
  else{
    struct Node*temp=*root,*helper=*root;
    /*Find middle element of linked list*/
    while(temp!=NULL&&temp->next!=NULL&&temp->next->next!=NULL){

      helper=helper->next;
      temp=temp->next->next;
    }

    if(helper!=NULL&&helper!=*root){
      /*assign middle node address to temp pointer*/
      temp=helper;
      
      /*Point first node of linked list*/
      helper=*root;
      /*Move next memory block address*/
      *root=(*root)->next;
      /*Assign first node next pointer value is (middle node next memory block)*/
      helper->next=temp->next;
      /*middle node next pointer value are assign to first node of linked list*/
      temp->next=helper;
    }else{
      printf("\nOnly one element of linked list");
    }

  }
}

int main(){
  /* start program execution are here */
  struct Node*root=NULL;
  printf("\n Case 1: Empty Linked list \n  ");

  /*show_data functions showing data on list*/
  show_data(root);
  
  printf("\n case 2: When linked list are not empty \n ");
  
    /* Assume that following data are inserted */

  /* 1--->2--->3--->4--->5--->6--->7--->8 */
  
  insert_data(&root,1);
  insert_data(&root,2);
  insert_data(&root,3);
  insert_data(&root,4);
  insert_data(&root,5);
  insert_data(&root,6);
  insert_data(&root,7);
  insert_data(&root,8);

  printf("\n Before move ");
   /*show_data functions showing result after inserted all newly created node*/
  show_data(root);

  move_node(&root);
  printf("\n After move ");
  show_data(root);

  /*removing linked list node*/
  remove_node(&root);
  
  /*end execution*/
}

Output

 Case 1: Empty Linked list 
  Empty linked List

 case 2: When linked list are not empty 
 
 Before move linked list :1  2  3  4  5  6  7  8  
 After move linked list :2  3  4  1  5  6  7  8  

 Free nodes of linked linked

Visualization

Circular Single Linked list

Circular Doubly Linked list

Sorting

Move first node a middle of given linked list

Recommended Posts:

Visualization

Comments