Learner Level
Implement the mergeTwoSortedLinkedLists method that merges two sorted linked lists and returns the sorted values.
The input contains two sorted linked-list value sequences, a and b, along with their sizes sizeA and sizeB.
Each array represents a sorted linked list from head to tail. Your task is to merge both lists and return one sorted sequence containing all values.
For example, merging [1,2,4] and [1,3,4] should return [1,1,2,3,4,4].
Use two pointers, one for each sorted list.
Compare the current values from both lists. Add the smaller value to the result and move that pointer forward. If both values are equal, either one can be added first.
When one list is finished, append all remaining values from the other list because they are already sorted.
Pseudocode:
function mergeTwoSortedLinkedLists(a, sizeA, b, sizeB):
i = 0
j = 0
result = empty array
while i < sizeA and j < sizeB:
if a[i] <= b[j]:
append a[i] to result
i++
else:
append b[j] to result
j++
while i < sizeA:
append a[i] to result
i++
while j < sizeB:
append b[j] to result
j++
return result