题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
这道题我的第一思路这样的：可以先遍历这两个排序的链表，把遍历的结果存放在一个集合中，然后调用库函数arrays.sort方法完成排序，之后，根据这些排好序的结果重新创建一个链表，即为合并之后但仍然排序的链表。但是这种思路需要额外的list和创建链表的空间开销，而且时间复杂度最快也是o(nlogn)。所以不是很理想。第二种思路是这样的：因为两个链表都是排序的，所以可以先比较两个链表的头结点，这样就确定了合并之后链表的第一个节点，之后再比较两个链表的第二个节点（原来较大值与较小值所属链表的第二个节点进行比较），这样依次就能确定合并链表的第二个、第三个节点，故明显是一个递归的过程。参照这个过程实现代码如下（已被牛客ac）：
上面的递归代码看起来很简洁，但是非递归代码也是需要掌握的，代码如下：