# Thread: How can I optimize this function that merges two ordered linked lists?

1. ## How can I optimize this function that merges two ordered linked lists?

I am learning data structures in C and, in one exercise, I was asked to create a function that merges two ordered linked lists into a single ordered linked list. Here it is:

Code:
```static struct listnode *
merge(struct listnode *a, struct listnode *b)
{

if (a == NULL)
return b;
if (b == NULL)
return a;

if (a->data <= b->data) {
a = a->next;
}
else {
b = b->next;
}

while (a != NULL && b != NULL) {
if (a->data <= b->data) {
p->next = a;
a = a->next;
} else {
p->next = b;
b = b->next;
}
p = p->next;
}

if (a != NULL)
p->next = a;
if (b != NULL)
p->next = b;

}```
But it is full of ifs and repeated conditions, and I think my function is unnecessarily verbose. How can I optimize this function to something more short and elegant?

Here's the struct:

Code:
```struct listnode {
char data;
struct listnode *next;
};``` 2. Code:
```typedef struct listnode {
char data;
struct listnode *next;
} ListNode;```
Code:
```ListNode *merge(ListNode *a, ListNode *b)
{

while (a && b) {
if (a->data <= b->data) {
*curr = a;
a = a->next;
} else {
*curr = b;
b = b->next;
}
curr = &(*curr)->next;
}

if (a) *curr = a;
if (b) *curr = b;

}```
Or recursively (but "inefficient" since it's not tail recursion) :
Code:
```ListNode *merge2(ListNode *a, ListNode *b )
{
if (a && (!b || a->data <= b->data))
{
a->next = merge2(a->next, b);
return a;
}
else if (b)
{
b->next = merge2(a, b->next);
return b;
}
return NULL;
}``` 3. The recursive version is better written like this:
Code:
```ListNode *merge2(ListNode *a, ListNode *b )
{
if (!a) return b;
if (!b) return a;

if (a->data <= b->data)
{
a->next = merge2(a->next, b);
return a;
}

b->next = merge2(a, b->next);
return b;
}``` 4. Originally Posted by john.c Code:
`     ListNode *head = NULL, **curr = &head;`
Why did you declared curr as a pointer to pointer? It could be just a regular pointer, couldn't it? 5. No. If curr could just be a single-level pointer I would've wrote it that way since it would be simpler. The reason you need the second level of indirection is that we don't want curr to hold the value of a pointer, but instead to hold the address of where that value is stored.

By storing the address where the pointer value is stored we can write to that address by dereferencing curr, modifying the value (which itself happens to be a pointer) at that address. It is this ability that allows us to eliminate some of the repetitive code in your attempt. The way you did it, there is a fundamental difference between "head" and all of the "next" pointers, and you need separate code to deal with that difference. But by using another level of indirection and pointing to the place where the pointers are stored, the "head" storage location and the "next" storage locations all look the same and can be handled by the same piece of code. 6. This is similar to john.c's answer, but only checks for a == NULL or b == NULL as needed, instead of a while that checks both for every node moved.

Code:
```ListNode * MergeLists(ListNode *a, ListNode *b)
{
if(a == NULL)                       /* if either list empty, */
return b;                       /*  return the other */
if(b == NULL)
return a;
while(1){                           /* merge the lists */
if(a->data <= b->data){
*curr = a;
curr = &(a->next);
a = *curr;
if(a == NULL){
*curr = b;
break;}}
else{
*curr = b;
curr = &(b->next);
b = *curr;
if(b == NULL){
*curr = a;
break;}}}
}``` 7. I discover how to use dummy nodes whose .next element points to the beginning of a list.
This is how I defined merge:

Code:
```struct listnode *
merge(struct listnode *a, struct listnode *b)
{
struct listnode *p;

while (a != NULL && b != NULL) {
if (a->data <= b->data) {
p->next = a;
a = a->next;
} else {
p->next = b;
b = b->next;
}
p = p->next;
}
if (a != NULL)
p->next = a;
if (b != NULL)
p->next = b; Popular pages Recent additions data structure, data structures, data structures in c, learning, learning c 