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 = [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:

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 nextof tempNode to l1 and move l1 forward.
5. Otherwise, assign nextof 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 nextof 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