Coding-Community-Contributions/LeetCode_Merge_Two_Sorted_LinkedLists at main · Manish1Gupta/Coding-Community-Contributions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
private:
    void insertAtPos(ListNode* &ltemp, ListNode* &stemp){
        ListNode* NodeToInsert=ltemp;
        ltemp=ltemp->next;
        NodeToInsert->next=stemp->next;
        stemp->next=NodeToInsert;
        stemp=stemp->next;
    }
    ListNode* solve(ListNode* &small, ListNode* &large){
        ListNode* stemp=small;
        ListNode* ltemp=large;
        ListNode* sprev=stemp;
        if(stemp->next==NULL){
            stemp->next=ltemp;
            return small;
        }
        while(stemp!=NULL && ltemp!=NULL){
            if(ltemp->val >= stemp->val && stemp->next==NULL)
                insertAtPos(ltemp, stemp);
            else if(ltemp->val >= stemp->val && stemp->next->val>=ltemp->val)
                insertAtPos(ltemp, stemp);
            else{
                sprev=stemp;
                stemp=stemp->next;
            }
        }
        if(ltemp!=NULL){
            sprev->next=ltemp;
        }

        return small;
    }
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL)
            return list2;
        if(list2==NULL)
            return list1;
        if(list1->val >= list2->val)
            return solve(list2, list1);
        else
            return solve(list1, list2);
    }
};