Merge Two Sorted Lists - Linked List - Easy - LeetCode

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * public int val;
 * public ListNode next;
 * public ListNode(int val=0, ListNode next=null) {
 * this.val = val;
 * this.next = next;
 * }
 * }
 */
public class Solution {
 public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
 if(l1==null){
 return l2;
 }
 
 if(l2==null){
 return l1;
 }
 
 ListNode head=null;
 ListNode temp = null;
 while(l1!=null && l2!=null){
 if(l1.val<l2.val){
 if(head==null){
 head=l1;
 temp=head; 
 }
 else{
 temp.next=l1;
 temp=temp.next;
 }
 l1=l1.next;
 }
 else{
 if(head==null){
 head=l2;
 temp=head; 
 }
 else{
 temp.next=l2;
 temp=temp.next;
 }
 l2=l2.next;
 }
 }
 
 if(l1!=null){
 temp.next = l1;
 }
 
 if(l2!=null){
 temp.next = l2;
 }
 
 return head;
 }
}

Time Complexity: O(m+n)

Space Complexity: O(m+n) to store the result

Here m and n are the lengths of linked lists.