Below is the C program for rearranging the linked list (not copying the elements), in such a way that, first odd elements next even elements should come as shown below. I faced this question in Amazon Interview first round. So Sharing the program here.
Input list: 1 2 3 4 5 6 7 8 9 10
OutputList: 1 3 5 7 9 2 4 6 8 10
Input Linked List:
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19
Resulted List:
1->3->5->7->9->11->13->15->17->19->2->4->6->8->10->12->14->16->18
Input list: 1 2 3 4 5 6 7 8 9 10
OutputList: 1 3 5 7 9 2 4 6 8 10
#include<stdio.h> #include<stdlib.h> //linked list structure struct node { int info; struct node *next; }; //making typdef so we can use Node instead of 'struct node' typedef struct node Node; //rearranging the linked list in such a way that odd no.s first //and then even no. Node* oddEven(Node* h) { Node* tempNode = h; Node* oddEnd = NULL,*oddHead = NULL; Node* evenHead = NULL, *evenEnd = NULL; while( tempNode != NULL) { if(!(tempNode->info%2)) { if(evenHead == NULL) evenHead = tempNode; else evenEnd->next = tempNode; evenEnd = tempNode; } else { if(oddHead == NULL) oddHead = tempNode; else oddEnd->next = tempNode; oddEnd = tempNode; } tempNode = tempNode->next; } h = oddHead; oddEnd->next = evenHead; evenEnd->next = NULL; return h; } //inserting node or creating the list or adding the element @ end Node* insert(Node *h, int info) { Node *tempHead=h; Node *newNode = (Node*)malloc(sizeof(Node)); newNode->info = info; newNode->next = NULL; if(tempHead == NULL) // if the list has zero elements. make new node as a head { h=newNode; } else if(tempHead->next==NULL) // if the list is having only one node { tempHead->next = newNode; } else { Node *tempNode = h; while(tempNode->next != NULL) // if the list has more than one node, so moving to the last node { tempNode = tempNode->next; } tempNode->next = newNode; // appending the new node at the end } return h; } /***************************************************************************** for displaying the nodes in the list *****************************************************************************/ void display(Node *h) { Node *temp = h; while (temp->next!=NULL) { printf("%d->",temp->info); temp = temp->next; } printf("%d\n",temp->info); } int main() { Node *head = NULL; int i,n,element,choice,pos,size; for (i=1;i<20;i++) { head = insert(head,i); } display(head); head=oddEven(head); display(head); }Output:
Input Linked List:
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19
Resulted List:
1->3->5->7->9->11->13->15->17->19->2->4->6->8->10->12->14->16->18