题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路
我们可以通过递归将问题转换为子问题。假设我们要合并
l1=[1,2,3]
l2=[0,2,4]
在每次合并时,我们可以比较当前节点值的大小然后递归地去修改 next。例如对这个用例,有:
l1: 1_1->1_2->1_3 l2: 2_0->2_2->2_4
^ ^
l1->val > l2->val ->
l2->next=merge(l1, l2->next)
l1: 1_1->1_2->1_3 l2: 2_0->2_2->2_4
^ ^
l2->val > l1->val ->
l1->next=merge(l1->next, l2)
...
依次类推,最后就可以将链表按顺序合并了。
最终代码: