Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

 

 to see which companies asked this question

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* mergeTwoLists(struct ListNode *l1, struct ListNode *l2){        if (l1 == NULL && l2 == NULL) {            return NULL;        } else if (l1 == NULL) {            return l2;        } else if (l2 == NULL) {            return l1;        }        ListNode* phead;        ListNode* node;        ListNode* p1 = l1;        ListNode* p2 = l2;        if (p1->val <= p2->val) {            phead = p1;            p1 = p1->next;        } else {            phead = p2;            p2 = p2->next;        }        node = phead;        while (p1 != NULL && p2 != NULL) {            if (p1->val <= p2->val) {                node->next = p1;                p1 = p1->next;            } else {                node->next = p2;                p2 = p2->next;            }            node = node->next;        }        node->next = p1 ? p1 : p2;        return phead;    }};