/**

 * Definition of singly-linked-list:

 * class ListNode {

 * public:

 *     int val;

 *     ListNode *next;

 *     ListNode(int val) {

 *        this->val = val;

 *        this->next = NULL;

 *     }

 * }

 */

class Solution {

public:

    /**

     * @param l1: ListNode l1 is the head of the linked list

     * @param l2: ListNode l2 is the head of the linked list

     * @return: ListNode head of linked list

     */

    ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {

        // write your code here

        if(!l1 && l2) return l2;

        else if(l1 && !l2) return l1;

        else if(!l1 && !l2) return NULL;

        ListNode *p;

        if(l1->val < l2->val){

            p=l1;

            p->next=mergeTwoLists(l1->next,l2);

        }

        else{

            p=l2;

            p->next=mergeTwoLists(l1,l2->next);

        }

        return p;

    }

};