Interview Q&A / Data Structures & Algorithms

1. How do you merge two sorted arrays into one sorted array?

   Use two pointers, one at the start of each array. Compare the two current elements, copy the smaller one to the result and move that pointer forward. When one array runs out, copy the rest of the other. This is O(n + m) time, much better than joining and sorting again.

   BeginnerIn-depthCoding3 min read
2. How do you merge two sorted linked lists into one sorted list?

   Use a dummy head and a tail pointer. Repeatedly attach the smaller of the two current nodes to the tail and advance that list. When one list ends, attach the rest of the other.

   BeginnerQuick answerCoding1 min read