Merge Two Sorted Linked Lists
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.
 */
Node* MergeLists(Node *headA, Node* headB)
{
    if (headA == NULL) {
        return headB;
    } else if (headB == NULL) {
        return headA;
    } else if (headA-&gt;data &lt;= headB-&gt;data) {
        headA-&gt;next = MergeLists(headA-&gt;next, headB);
        return headA;
    } else {
        headB-&gt;next = MergeLists(headA, headB-&gt;next);
        return headB;
    }
}