Merge Two Sorted Lists Blind 75 LeetCode Questions
Task description:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Example 2:
Input: list1 = [], list2 = []
Output: []Example 3:
Input: list1 = [], list2 = [0]
Output: [0]Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
Reasoning:
LinkedList is another widely used data structure. It could be singly linked or doubly linked.
For this particular task we can assume that we work with singly linked version. As you can see every linked list consists of small pieces called Links or Node.
As you can see from pictures and code above every LinkedNode stores link to the next LinkedNode. The first LinkedNode is usually called head where as last one is called tail. With singly linked version we can only traverse from a head to tail of the list and there’s no way to return to previous node once we stepped forward. Doubly linked version allows us to traverse in both directions because every ListNode stores pointers to next and previous ListNodes.
Solution:
This time I provide full code for the solution and we’ll discuss it
The first thing we do is we create a dummy node for storing link to the future head of merged linked list, as I said previous every LinkedList has head.
We also need a current node for storing link of current node, so we can use it to attach next node to it
We iterate through both lists till pointers to next nodes are not null. On every such step we’re looking for a node with minimal value stored in it. We move pointer to the next for LinkedList which has current node with minimal value. Eventually one of the pointers of both are null.
The last things we need to do is to attach rest of LinkedList which still has some values to our current pointer and return a head of newly created LinkedList.
Solution above has linear time complexity and doesn’t use additional memory(In terms of big O notation additional pointers can be ommited)
See you in the next article✌️✌️✌️✌️✌️✌️✌️
Level Up Coding
Thanks for being a part of our community! Before you go:
- 👏 Clap for the story and follow the author 👉
- 📰 View more content in the Level Up Coding publication
- 🔔 Follow us: Twitter | LinkedIn | Newsletter
