算法

(二路归并) O(n)

新建头部的保护结点s，设置p指针指向s。

若当前l1指针指向的结点的值val比l2指针指向的结点的值val小，则令p的next指针指向l1，且l1后移；否则指向l2，且l2后移。

然后p指针按照上一部设置好的位置后移。

循环以上步骤直到l1或l2为空。

将剩余的l1或l2接到p指针后边。

时间复杂度

两个链表各遍历一次，所以时间复杂度为O(n)