Merge sorting linked lists

This works as expected and I want to get this code reviewed so that I can improve my coding ability.

I am concerned about readability and the quality of the code

```
#include
#include

struct node
{
int element;
struct node *next;
};

struct node mergeList(struct node list1, struct node *list2)
{
struct node root = NULL, cur = NULL;

if(list1 == NULL)
{
return list2;
}

if(list2 == NULL)
{
return list1;
}

while( (list1 != NULL) && (list2 != NULL) )
{
struct node *tmp = malloc(sizeof(struct node));
if( list1->element element )
{
tmp->element = list1->element;
tmp->next = NULL;
list1 = list1->next;
}
else
{
tmp->element = list2->element;
tmp->next = NULL;
list2 = list2->next;

}
if(root == NULL)
{
root = tmp;
cur = root;
}
else
{
cur->next = tmp;
cur = tmp;
}

}

while(list1 != NULL)
{
struct node *tmp = malloc(sizeof(struct node));
tmp->element = list1->element;
tmp->next = NULL;
cur->next = tmp;
cur = tmp;
list1 = list1->next;
}
while(list2 != NULL)
{
struct node *tmp = malloc(sizeof(struct node));
tmp->element = list2->element;
tmp->next = NULL;
cur->next = tmp;
cur = tmp;
list2 = list2->next;
}

return root;

}

void findMid(struct node *root, struct node list1, struct node list2)
{

struct node *slow;
struct node *fast;
printf("\nIn Findmis\n");
if( (root == NULL) || (root->next == NULL) )
{
*list1 = root;
*list2 = NULL;
return;
}
else
{

slow = root;
fast = root->next;
while (fast != NULL)
{
fast = fast->next;
if(fast!=NULL)

Preliminaries

Your compiler should have warned you that in main(), you never use list2. You do compile with warnings turned on, I hope?

Usually, the first node of a linked list is called the head. "Root" usually refers to the top of a tree.

mergeList() and findMid() are helper functions, which are designed to be used exclusively to support mergeSort(). It's a good habit to declare helper functions with the static modifier, so that they will be invisible to code in other .c files.

findMid()

The function could be better named, I think. "Find" sounds like a passive action, so you wouldn't expect that it might modify its inputs (which it does at the end: slow->next = NULL). I suggest calling it bisectList() instead.

Calling the function will always result in setting *list1 to root, so why bother making list1 an out-parameter? Going a step further, if there's only one output (list2), you can just return it normally.

So, the function could become static struct node bisectList(struct node head). Here's a more compact implementation.

/**
 * Returns a pointer to a node near the middle of the list,
 * after having truncated the original list before that point.
 */
static struct node *bisectList(struct node *head)
{
    /* The fast pointer moves twice as fast as the slow pointer. */
    /* The prev pointer points to the node preceding the slow pointer. */
    struct node *fast = head, *slow = head, *prev = NULL;

    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        prev = slow;
        slow = slow->next;
    }

    if (prev != NULL)
    {
        prev->next = NULL;
    }
    return slow;
}

mergeList()

The function signature looks fine. There is altogether too much code, though.

One major problem, which @rolfl alluded to, is that you are duplicating every node that you encounter. Rather, you should be able to merge the lists just by manipulating the next pointers of the existing nodes.

To start with, you can eliminate the two special cases before the loop. (That meant, by the way, that your function not only leaked memory, it also had an inconsistent memory management policy: sometimes it would duplicate the list, and sometimes not.)

Once we have decided not to duplicate the nodes, the epilogue becomes trivial, and the last two loops can go away.

The code duplication within the main loop can be reduced by using a pointer to a pointer (which I call **min), referring to whichever list a head with the smaller value. The if (root == NULL) special case can be removed by initializing a pointer to a dummy head node.

static struct node* mergeList(struct node *list1, struct node *list2)
{
    struct node dummy_head = { 0, NULL }, *tail = &dummy_head;

    while ( (list1 != NULL) && (list2 != NULL) )
    {   
        struct node **min = (list1->element element) ? &list1 : &list2;
        struct node *next = (*min)->next;
        tail = tail->next = *min;
        *min = next;
    }
    tail->next = list1 ? list1 : list2;
    return dummy_head.next;
}

mergeSort()

It would be more natural to accept a struct node and return a struct node , I think.

You left in some printf() calls for debugging. Why not take advantage of the existing printList() function for that?

Most of the improvements are just natural consequences of the changes suggested above.

struct node *mergeSort(struct node *head) 
{   
    struct node *list1 = head; 
    if ( (list1 == NULL) || (list1->next == NULL) )
    {   
        return list1;
    }   

    struct node *list2 = bisectList(list1);

    printf("\nList1 = "); printList(list1);
    printf("\nList2 = "); printList(list2);

    return mergeList( mergeSort(list1), mergeSort(list2) );
}

Conclusion

Your understanding of the mergesort algorithm is generally sound. However, there were some massive memory leaks, and the implementation was verbose. Try to look for opportunities to design more natural function interfaces and reduce special cases.

StackExchange Code Review Q#62157, answer score: 6