reorder linked list as even elements followed by odd elements

#include <stdio.h>
#include <stdlib.h>


typedef struct node {
int data;
struct node *next;
}Node;

typedef Node * List;


/*
arranges the list as event elements followed by odd elements in single pass
*/
void evenOddList(List l){

if(!l) return;

Node *even = NULL,
*odd = NULL,
*start = NULL;

if(l->data & 1)
odd = l;
else
even = l;

l = l->next;

while(l) {

if(l->data & 1) {//odd

if(odd)
odd->next = l;
else
start = l;

odd = l;

}else { //even

if(even)
even->next = l;
else
start = l;

even = l;
}

l = l->next;
}

if(start) {
if(start->data & 1) {//odd

even->next = start;
odd->next = NULL;

}else {//even

odd->next = start;
even->next = NULL;
}
}

}


List append(List l, int e) {

static Node *end = NULL;

Node *n = calloc(sizeof(Node), 1);

n->data = e;

if(end) {
end->next = n;
}else {
l = n;
}

end = n;

return l;

}


void printList(List l) {

Node *n = l;

while(l) {

printf("%d ", l->data);

l = l->next;
}

printf("\n");
}


int main() {

int a[]= {13, 11, 28, 45, 58, 69, 34, 23, 86};


List l = NULL;

int i;

for(i = 0; i < sizeof(a)/sizeof(int); ++i) {

l = append(l, a[i]);

}


printList(l);

evenOddList(l);

printList(l);
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s