Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
分析：这道题我们新建新的链表，并且此题运用递归手法还是很好做的。首先我们从合并两个链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点，反之，链表2的头结点将是合并后链表的头结点。我们继续合并两个链表中剩余的结点。在两个链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和前面步骤是一样的。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if(l1==NULL) return l2; else if(l2==NULL) return l1; ListNode *pMerge=NULL; if(l1->val<l2->val) { pMerge=l1; pMerge->next=mergeTwoLists(l1->next,l2); } else { pMerge=l2; pMerge->next=mergeTwoLists(l1,l2->next); } return pMerge; } };
Merge Two Sorted Lists,布布扣,bubuko.com
原文：http://www.cnblogs.com/awy-blog/p/3597316.html