# Merge Two Sorted Linked Lists

I solved this problem in C++. I was having trouble though understanding what return headA; and return headB; returns after going back down the recursion tree. A code review is also appreciated!

Youâ€™re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.

````/*   Merge two sorted lists A and B as one linked list   Node is defined as    struct Node   {      int data;      struct Node *next;   } */ #include <iomanip>  Node* MergeLists(Node *headA, Node* headB) {     // check if either linked list is empty, then return the other one. when doing recursive, a new headA and headB will be passed in, so it will add the entire list correctly   if (headA == NULL) {       return headB;   } else if (headB == NULL) {       return headA;   } else { // if neither empty go into this block       if (headA->data <= headB->data) {           headA->next = MergeLists(headA->next, headB);           // returns the entire linked list after the recursion parses it in the correct order           // not too sure what is returned going down the recursion tree           // headA = 1 -> 3 -> 5 -> 6 -> NULL           // headB = 2 -> 4 -> 7 -> NULL           // would it return 6, 5, 3, 1, 1->2->3->4->5->6->7 after recursion tree?           return headA;       } else {           headB->next = MergeLists(headA, headB->next);           // return 7, 4, 2 after recursion tree?           return headB;       }   } } `
```

Replay

An iterative algorithm

Of course, you can do the job recursively. However, if you merge large lists that way, there is a chance of running out the stack space. Also, the space complexity of your recursive method is \\$\Theta(n)\\$ (on the stack). Using iteration, you can reduce the space complexity to \\$\Theta(1)\\$, and that is how:

``````Node* MergeLists(Node *headA, Node* headB)
{
{
}

{
}

Node* tail;

{
}
else
{
}

{
{
}
else
{
}
}

{
}

{
}

}
```
```

Coding conventions

You use a consistent coding style what comes to spacing, braces, etc. However, I suggest you don't use more than 80 characters on any line; for example:

``````// check if either linked list is empty, then return the other one. when doing recursive, a new headA and headB will be passed in, so it will add the entire list correctly
```
```

Why not split it in more than one line:

``````// check if either linked list is empty, then return the other one.
// when doing recursive, a new headA and headB will be passed in,
// so it will add the entire list correctly
```
```

Hope that helps.

Your solution is fine, subject to the caveat that the use of recursion imposes a limit on the length of your lists, due to the possibility of stack overflow.

Your comments betray a sense of insecurity about how it works, though. Just consider what happens locally, and trust that recursion will take care of the rest.

I also suggest un-nesting the `else` block.

``````/**
* Recursively merge two sorted lists by manipulating node pointers.
* Returns the head of the merged list.
*/
{
} else if (headB == NULL) {
} else {
}
}
```
```
Category: c# Time: 2016-07-28 Views: 0