sorting - How can you merge sort two list nodes without creating a third? -

sorting - How can you merge sort two list nodes without creating a third? -

given 2 list nodes, need implement merge sort without creating 3rd list node. if list node 1 has 1,2,4,6,8 , list node 2 has 3,5,9,11,15, output should in first list node 1,2,3,4,5,6,8,9,11,15. i'm stuck. it's easy 3rd list node don't know how reliably two.

given 2 lists a, b.

im not sure if lists sorted, if loop though both arrays , insert elements array b array when needed. if b longer, append rest of (once has been iterated through) onto a.

else if, longer you're done when b done looping.

otherwise have offset , prepend sorted info a, using a[0, offset] 3rd array.

another alternative append of b onto , sort in place using normal merge sort.

none of these options require new array , of them can optimized not take more memory.

sorting merge