LeetCode21——Merge two sorted lists——Iteration or recursion

一道常规的题目，即合并两个有序的链表，题面如下：

合并(Merge)这一步往往是归并排序(MergeSort)的一个子步骤，一个需要注意的点是。由于我们合并的是链表，所以不需要额外申请存储空间，完全可以通过改变指针的方式来实现两个链表的有序合并，所以在合并过程中有new开辟新的节点的操作一定不是最优的。反过来说，如果是向量这种连续的存储空间实现归并，那么是需要额外空间来支持的。
比较易于掌握的代码写法当然是迭代式合并，为了方便处理先申请一个头节点Result来简化操作，也是为了记录下最终合成链表的开始位置(一定是Result->next)，LastNode指的则是下一个节点将要插入的位置，代码如下：

		ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    
        /*get a dummy node for the Result list*/
        ListNode* Result = new ListNode();
        ListNode* LastNode = Result;

        /*start merging the 2 lists*/
        while(l1 && l2)
        {
    
            /*if the l1->val <= l2->val*/
            if(l1->val <= l2->val)
            {
    
                LastNode->next = l1;
                LastNode = LastNode->next;
                l1 = l1->next;
            }    
            else
            {
    
                LastNode->next = l2;
                LastNode = LastNode->next;
                l2 = l2->next;
            }
        }
        /*deal with the remained part of list*/
        LastNode->next = l1 ? l1 : l2;
        return Result->next;
    }

这种做法利于掌握，但少了一些灵气。
邓俊辉老师在某节课课件开头写：迭代乃人工，递归方神通。这道题也可以用递归的方式更加巧妙地写完，首先写一个递归合并函数merge。可以看到，通过下面这个函数可以将l1和l2递归的挂接到Result所指示的指针后面，由于每次递归时传递的均是Result->next，所以Result本身的值并没有改变，也就不用像迭代那样保留一个LastNode来记录最后一个要插入的位置。递归基就是当其中一个链表为空时，经过简单处理即可返回。

void merge(ListNode*& Result, ListNode* l1, ListNode* l2)
    {
    
        /* recursion base */
        if(!l1 || !l2)  
        {
    
            Result->next = l1 ? l1 : l2;
            return; 
        }
        else if(l1->val <= l2->val)
        {
    
            Result->next = l1;
            merge(Result->next, l1->next, l2);
        }
        else
        {
    
            Result->next = l2;
            merge(Result->next, l1, l2->next);
        }
    }

随后在主函数中调用之即可：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    
      /*recursive method*/
      /*get a dummy node for the Result list*/
      ListNode* Result = new ListNode();
      merge(Result, l1, l2);
      return Result->next;
 }