21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/
Solution 0. Use a dummy node as the head. (9 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(INT_MIN);
        ListNode* tail = &head;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            }
            else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1? l1:l2;
        return head.next;
    }
Solution 1.0 Recursion. Slow but simple. (19 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val > l2->val) return mergeTwoLists(l2, l1);
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
Solution 1.1  (12 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val > l2->val) return mergeTwoLists(l2, l1);
        ListNode* head = l1;
        ListNode* p;
        while(true) {
            while(l1->next && l1->next->val <= l2->val) l1 = l1->next;
            p = l1;
            l1 = l1->next;
            p->next = l2;
            if(!l1) return head;
            while(l2->next && l2->next->val <= l1->val) l2 = l2->next;
            p = l2;
            l2 = l2->next;
            p->next = l1;
            if(!l2) return head;
        }
    }