# cPP, merge , O(nlogn)timecomplexity ,O(1)spacecomplexity

• /**

• Definition for singly-linked list.

• struct ListNode {

• ``````int val;
``````
• ``````ListNode *next;
``````
• ``````ListNode(int x) : val(x), next(NULL) {}
``````
• };
/
class Solution {
public:
ListNode
if(head == NULL || head->next == NULL)
{
}

`````` ListNode* slow;

slow->next = NULL;

ListNode* p = sortList(head);
ListNode* q = sortList(headTwo);

return merge(p,q);
``````

}

{
ListNode* slow = head;
ListNode* fast = head;

`````` while(fast->next != NULL && fast->next->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}

return slow;
``````

}

ListNode* merge(ListNode* p,ListNode* q)
{
ListNode* lc;
ListNode* pc;

`````` if(p->val < q->val)
{
lc = pc = p;
p = p->next;
}
else
{
lc = pc = q;
q = q->next;
}

while(p != NULL && q != NULL)
{
if(p->val < q->val)
{
pc->next = p;
p = p->next;
pc = pc->next;
}
else
{
pc->next = q;
q = q->next;
pc = pc->next;
}
}

if(p != NULL)
{
pc->next = p;
}
if(q != NULL)
{
pc->next = q;
}

return lc;
``````

}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.