25. 合并两个排序的链表
1. 描述
输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
2. 例子
示例 1:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
3. 限制
- 0 <= 链表长度 <= 1000
4. 题解
n 是 result 中的节点数
时间复杂度: O(n)
空间复杂度: O(1)
class Solution
{
public:
// ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
ListNode* mergeTwoLists(ListNode *m_l1, ListNode *m_l2)
{
auto result = new ListNode();
result->next = m_l1;
auto iter = result;
while(m_l1 && m_l2)
{
if(m_l1->val <= m_l2->val)
{
iter->next = m_l1;
m_l1 = m_l1->next;
}
else
{
iter->next = m_l2;
m_l2 = m_l2->next;
}
iter = iter->next;
}
iter->next = (m_l1 ? m_l1 : m_l2);
return result->next;
}
};