Monday, November 5, 2012

C Program for Rearranging linked list first odd next even numbers

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

#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

Popular Posts