Tue 08 Jan 2019
Merge Two Sorted Lists
Tags: programming leetcode code
Merge two sorted linked lists and return it as a new list.1The new list should be made by splicing together the nodes of the first two lists.
It’s an easy problem in Leetcode for practicing linked list. It’s similar to the merge step of the Merge sort.
Brute force algorithm
Merge the both list together and sort the returning list. This will take complexitiy of @L O(n + m)log(n + m) @L , where n & m are length of each two list.
More efficient solution
Similary to algorithm used in merging step of Merge Sort, we can acheive @L O(n + m) @L time complexity. Traverse both the list together, and insert the smallest value into the new list.
comments powered by