/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* S1, ListNode* S2) {

        if(!S1 && !S2) return NULL;
        else if(!S1) return S2;
        else if(!S2) return S1;

        if(S1->val > S2->val)
        {
            swap(S1, S2);
        }

        ListNode* temp_S1 = S1;
        ListNode* temp_S2 = S2;

        while(temp_S1->next && temp_S2)
        {
            if(temp_S1->next->val >= temp_S2->val)
            {
                ListNode* temp = temp_S1->next;
                temp_S1->next = temp_S2;
                temp_S2 = temp;
                temp_S1 = temp_S1->next;
            }
            else if(temp_S1->next->val < temp_S2->val)
            {
                temp_S1 = temp_S1->next;
            }
        }

        while(temp_S2)
        {
            temp_S1->next = temp_S2;
            temp_S2 = temp_S2->next;
            temp_S1 = temp_S1->next;
        }


        return S1;
    }
};