题目要求:合并两个单向已排序的链表l1和l2,返回新的链表。
思路:该问题跟合并两个已排序的数组很像,合并两个已排序的数组是使用三个指针,从尾向头扫描,不断加入到数组中。而单向链表不能从尾往头加,这时候考虑也用两个“指针”从头往尾扫,加入到第三个新的链表中。
起始状态:比较l1的头结点和l2的头结点的大小,让较小的(假如为l1)作为新的链表的头节点,然后再递归地比较l1.next和l2的“头节点”(l1.next可以看做一个新的链表,它去除了刚刚加入新链表的数)直到两个链表中有一个为空链表为止。
还需要考虑特殊情况,当l1为空或者l2为空时,剩下的另一个链表的数据可以直接追加到新链表中,不需要再比较。
最终返回新链表的头节点即可。
代码如下。