Merge Two Sorted Lists
Problem
You are given the heads of two sorted linked lists
list1
andlist2
.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.
Pseudocode
Solution
Time and Space Complexity
Time
traversing the longest sorted linked list - O(N)
assigning node.next to new list - O(1)
Total - O(N)
Space
creating a new sorted linked list, sum of both input - O(N)
Total - O(N)
Last updated