Merge Two Sorted Lists(LinkedList) -Explained with pictures - LeetCode qn solution C++
Original Problem Link: https://leetcode.com/problems/merge-two-sorted-lists/
Problem:
Merge two sorted linked lists and return it as a sorted list.
The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
Constraints: The number of nodes in both lists is in the range [0, 50]. -100 <= Node.val <= 100 Both l1 and l2 are sorted in non-decreasing order.
SOLUTION:
******************************************************************
******************************************************************
******************************************************************
******************************************************************
******************************************************************
******************************************************************
******************************************************************
******************************************************************
Fast forward to few steps--->
******************************************************************
******************************************************************
******************************************************************
Final list will be:
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 46 47 48 49 50 | /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==NULL ) return l2; if(l2==NULL) return l1; ListNode* i=l1; ListNode* in=l1->next; ListNode* j=l2; ListNode*jn=l2->next; ListNode* from=(i->val<=j->val)?i:j; ListNode* head=from; ListNode* to=NULL; if(from==i) i=i->next; else j=j->next; while(i!=NULL && j!=NULL) { to=(i->val<=j->val)?i:j; if(to==i) i=i->next; else j=j->next; from->next=to; from=to; } if(i==NULL) from->next=j; else from->next=i; return head; } }; |
