Ah, this reminds me of a beautiful thing that a fine gentleman CB
Falconer posted once in comp.programmer. It was so elegant that my
normally bad memory still remembers it after some years.
You can simplify the merge by using a dummy node for the head of the
merged list rather than just a pointer. There was a question about
sentinels in another thread. This is similar.
struct node* SortedMerge(struct node* a, struct node* b)
{
struct node head[1], *tail;
// Since head is a dummy, head->next will be the "real" list head.
head->next = NULL;
tail = head;
// Merge lists
while(a && b)
{
if (a->data < b->data)
{
tail->next = a;
tail = a;
a = a->next;
}
else
{
tail->next = b;
tail = b;
b = b->next;
}
}
// Attach remaining list
tail->next = a ? a : b;
return head->next;
}
On Feb 23, 3:49 pm, Don <[email protected]> wrote:
> // Iterative merge
> struct node* SortedMerge(struct node* a, struct node* b)
> {
> struct node* head, tail;
>
> // Select first node
> if (a->data < b->data)
> {
> head = tail = a;
> a = a->next;
> }
> else
> {
> head = tail = b;
> b = b->next;
> }
>
> // Merge lists
> while(a && b)
> {
> if (a->data < b->data)
> {
> tail->next = a;
> a = a->next;
> }
> else
> {
> tail->next = b;
> b = b->next;
> }
> }
> // Attach remaining list
> tail->next = a ? a : b;
> return head;
>
> }
>
> On Feb 23, 3:41 am, rahul sharma <[email protected]> wrote:
>
>
>
> > struct node* SortedMerge(struct node* a, struct node* b)
> > {
> > struct node* result = NULL;
>
> > /* Base cases */
> > if (a == NULL)
> > return(b);
> > else if (b==NULL)
> > return(a);
>
> > /* Pick either a or b, and recur */
> > if (a->data <= b->data)
> > {
> > result = a;
> > result->next = SortedMerge(a->next, b);
> > }
> > else
> > {
> > result = b;
> > result->next = SortedMerge(a, b->next);
> > }
> > return(result);
>
> > }
>
> > a : 10 20 30
>
> > b : 10 25 35
> > wats the o/p??? 10 20 25 30 35
> > or 10 10 20 25 30????- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
