# Merge Two Sorted Lists | Leetcode #21 | Easy

In this post I will discuss the solution to the leetcode problem — 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 = Output: `

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:

The idea is simple. We need to iterate over both the lists simultaneously and create another list which consists of nodes from both the input lists. The only catch is to decide which list to pick the node from.

1. Create an empty node and call it `tempNode`
2. Create another node called `output` and assign it with `tempNode`
3. Iterate over both the lists `l1` and `l2` until one of them or both of them are completely traversed.
4. While iterating, if the node from `l1` has lesser value than node from `l2` , then assign `next`of `tempNode` to `l1` and move `l1` forward.
5. Otherwise, assign `next`of `tempNode` to `l2` and move `l2` forward.
6. In every iteration, don’t forget to move forward the `tempNode` which holds our final output.
7. After the loop, we either have both input lists traversed or one of them. So check which one is traversed and assign the other one to the `next`of `tempNode`
8. Since `output` was assigned to an empty node the actual output list starts from output.next and hence return it.
`public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  ListNode tempNode = new ListNode();  ListNode output = tempNode;  while(l1 != null && l2 != null) {    if (l1.val < l2.val) {      tempNode.next = l1;      l1 = l1.next;    } else {      tempNode.next = l2;      l2 = l2.next;    }    tempNode = tempNode.next;  }  tempNode.next = l1 == null ? l2 : l1;  return output.next;}`

Hope this helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems

--

--

I am a Software Engineer from India and working in Berlin, Germany. I write about technology, my experiences in Germany, travel in Europe.