题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

解题思路：

这里使用递归的方法。构造一个新的ListNode为tmp，当某个链表为空了，就返回另一个。核心是比较当前两个节点值大小，如果l2的小，那么对于l2的下一个节点和l1调用递归函数，将返回值赋值给 tmp->next ，然后返回tmp；否则就对于l1的下一个节点和l2调用递归函数，将返回值赋值给 tmp->next ，然后返回tmp，依次递归下去。

代码展示：

/** * 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; if (l2 == NULL) return l1; if (l1->val > l2->val) { ListNode *tmp = l2; tmp->next = mergeTwoLists(l1, l2->next); return tmp; } else { ListNode *tmp = l1; tmp->next = mergeTwoLists(l1->next, l2); return tmp; } } };