Let's try something new, in this thread I'm going to share some cheap coding tricks for problems you might or might not have. There is no fixed topic besides that everything posted here has something to do with programming and solving a very specific problem in a very obvious way. Also, you are free to post your own stuff here (one tip per post to make it easier to link to specific entries if that is ever going to be needed).
I'm going to start with a problem regarding linked list, how many of you ever had the problem of finding the middle of the linked list? I guess the answer is less than a dozen, but still, if you ever try to sort a linked list with anything else than bubble sort, you are going to come across this problem, and the most straightforward implementation is quite expensive.
The cheap coders way to solve this problem? Use two pointers to iterate and skip one entry with the second pointer, when the second one hits the end of the linked list the first one points to the middle.
Example:
typedef struct bucket_s
{
struct bucket_s *next;
} bucket_t;
bucket_t *findMiddle(bucket_t *head)
{
bucket_t *c1 = head;
bucket_t *c2 = head;
while(c2->next)
{
c1 = c1->next;
c2 = c2->next;
if(c2->next)
c2 = c2->next;
}
return c1;
}
