# Blind 75 - Merge Two-Sorted Lists

Iterate over both and store minimum one in current; Increment in the list from where minimum came. Once one of the lists is empty, empty the other one.

[Video]

Given two linked lists merge them into one sorted list.

## Approaches

### Unoptimized Solution: O(n) time complexity: Space: O(1)

Lines of code 38

Iterate over both and store minimum one in current; Increment in the list from where minimum came. Once one of the lists is empty, empty the other one.

This solution is highly unoptimized.

``````    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode current = null;

while(list1!=null && list2!=null){
ListNode minimum = null;

if(list1.val < list2.val){
minimum = list1;
list1 = list1.next;
} else{
minimum = list2;
list2 = list2.next;
}

current = minimum;
continue;
}
current.next = minimum;
current = current.next;
}

ListNode remaining = list1!=null? list1: list2;
while(remaining!=null){ // this iteration is unneccessary
if(current == null){
current = remaining;
} else {
current.next = remaining;
current = current.next;
}
remaining = remaining.next;
}

}``````

### Optimized solution

Java - LeetCode Discuss

Lines of code: 16

``````    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
while(list1!=null && list2!=null){
if(list1.val < list2.val){
current.next = list1;
list1 = list1.next;
} else{
current.next = list2;
list2 = list2.next;
}
current = current.next;
}

current.next = list1!=null? list1: list2;