Merge Two Sorted Lists
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
l1andl2are sorted in non-decreasing order.
Solution:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val =
val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode temp = new ListNode();
ListNode curr = temp;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
curr.next = l1;
l1 = l1.next;
}
else{
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
if(l1 != null){
curr.next = l1;
}
if(l2 != null){
curr.next = l2;
}
return temp.next;
}
}
Here, we are going to solve problem by iterating both the list at the same
time.
1) Initially create a new temp list and also curr list which
points to the temp list.
2) Iterate both the list in while loop equally, (until if any one of the list are not equal to null)
a) If l1 current value is less than or equal to
l2 current value, then make curr list ->
next points to l1 and make l1 points to next of
l1.
b) Else make curr list -> next points to l2 and
make l2 points to next of l2.
c) Update curr list.
3) If any one of the list are not null after all iteration, then update
it in curr list.
4) Return next of temp list [because head of temp list by default contains 0]
Related Posts:
Like us? Please do share with your friends ..!!
Follow us to receive updates instantly.
If you have any feedback/suggestions, leave it in a comment section or contact us through our contact page which will be helpful for us to improve.
Comments
Post a Comment