12.Merge Two Sorted Lists

Example:
Input: 1->2->4  , 1->3->4
Output: 1->1->2->3->4->4

Solution I: (Using extra space)

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {

        ListNode *head = NULL;

        ListNode *p = l1;
        ListNode *q = l2;
        ListNode *r = NULL;
        while (p != NULL && q != NULL)
        {
            ListNode *temp = new ListNode;
            temp->val = p->val;
            temp->next = NULL;

            if (p->val <= q->val)
            {
                if (head == NULL)
                {
                    head = temp;
                    r = head;
                }
                else
                {
                    r->next = temp;
                    r = r->next;
                }
                p = p->next;
            }
            else
            {
                ListNode *temp = new ListNode;
                temp->val = q->val;
                temp->next = NULL;
                if (head == NULL)
                {
                    head = temp;
                    r = head;
                }
                else
                {
                    r->next = temp;
                    r = r->next;
                }
                q = q->next;
            }
        }

        while (p != NULL)
        {
            ListNode *temp = new ListNode;
            temp->val = p->val;
            temp->next = NULL;
            if (head == NULL)
            {
                head = temp;
                r = head;
            }
            else
            {
                r->next = temp;
                r = r->next;
            }
            p = p->next;
        }

        while (q != NULL)
        {
            ListNode *temp = new ListNode;
            temp->val = q->val;
            temp->next = NULL;
            if (head == NULL)
            {
                head = temp;
                r = head;
            }
            else
            {
                r->next = temp;
                r = r->next;
            }
            q = q->next;
        }

        return head;
    }
};

Time Complexity O(m+n) and uses an Extra Space of O(n+m)

Solution II : (Using 3 pointers in constant space)

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {

        ListNode *head = NULL;
        ListNode *p = l1;
        ListNode *q = l2;
        ListNode *sort = NULL;

        if (p == NULL)
        {
            return q;
        }
        if (q == NULL)
        {
            return p;
        }

        if (p->val <= q->val)
        {
            sort = p;
            p = sort->next;
        }
        else
        {
            sort = q;
            q = sort->next;
        }
        head = sort;

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

        if (p == NULL)
        {
            sort->next = q;
        }
        else if (q == NULL)
        {
             sort->next = p;
        }

        return head;
    }
};

Time Complexity: O(m+n) and Space Complexity: O(1)