So again, here is how you can reverse a singly-linked list :
reverse(struct node ** start)
{
struct node * prev = NULL;
struct node * curr = *start;
while(curr)
{
swap(&prev, &curr->next);
swap(&curr, &prev);
}
*start = prev;
}
and here is for a doubly-linked list :
reverse(struct node **start)
{
struct node *curr = *start;
while(curr)
{
swap(&curr->prev, &curr->next);
if(!curr->prev)
*start = curr;
curr = curr->prev;
}
}
This is out of popular request.. nothing special about it. Below is a func that tells you whether the given number is a power of 2 :
int isPower(int i)
{
return !(i & (-i ^ i));
}
Hi … I know that its been too long since I had last posted into my blog and the main reason for that was a lack of interesting topic to discuss on my page. But last day I happen to meet a person(named Rajesh) who coined a simple question of re-ordering numbers in an array.
The situation is like this: we have an array of integers which contains randomly ordered numbers. We would wanna move all odd numbers to the beginning of the array and the even numbers to the end – still the ordering doesn’t matter. Below is the code that I believe would do the job in the least number of iterations:
int arr[]={1,2,3,4,5,6,7,8,9,10};
swap(int *p, int *q)
{
*p = *p ^ *q;
*q = *p ^ *q;
*p = *p ^ *q;
}
int checkeven(int value)
{
return !(value & 0x1);
}
int checkodd(int value)
{
return (value & 0x1);
}
int *find(int *start, int *end, int step, int (*cond)(int) )
{
while(((step > 0) && (start <= end)) || ((step < 0) && (end <= start)))
{
if(cond(*start))
break;
start += step;
}
return start;
}
reorder(int *start, int size)
{
int *end = start + size - 1;
while(1)
{
// find an even no. starting from the front
start = find(start, end, 1, checkeven);
//find an odd no. starting from the back
end = find(end, start, -1, checkodd);
if(start >= end)
break;
swap(start, end);
}
}
main()
{
reorder(arr, sizeof(arr)/sizeof(arr[0]));
}
