(21 points) Given $k$ singly linked lists, each of which has $n$ nodes. The numbers in the nodes of the $i$-th list are given by $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$, as shown in the figure below. Each of the $k$ lists has the numbers sorted in non-decreasing order, i.e., $a_{i,1} \le a_{i,2} \le \cdots \le a_{i,n}$, where $i$ is the index of the list. Professor Q asks the students to develop an algorithm to merge these k lists into one singly linked list sorted in non-decreasing order. Three students have come up with different algorithms, which are given below in pseudo code.

Student A: L1. Create an empty singly linked list $S$ to collect the result. L2. DO L3. Iterate over the numbers in the head nodes of the $k$ lists, and find the node with the smallest number, denoted as node $M$. L4. Remove node $M$ from the original list, and insert it into the result list $S$ from the tail. L5. UNTIL all original $k$ lists are empty L6. Return the result list $S$, which contains all nodes from the original $k$ lists and sorted in non-decreasing order.

Student B: L1. Create an empty singly linked list $S$ to collect the result. L2. Create an empty min heap $H$. L3. Remove the $k$ head nodes from the $k$ lists and insert them into $H$. Each node in $H$ also contains the index number $i$ of the list where it is from. L4. DO L5. Remove the min node $M$ from the heap. Insert this node into $S$ from the tail. Take note of the index number stored in $M$, denoted as $m$. L6. If list $m$ is not empty, remove the head node from list $m$ and insert it into $H$. L7. WHILE $H$ is not empty L8. Return the result list $S$, which contains all nodes from the original $k$ lists and sorted in non-decreasing order.

Student C: Call the recursive divide-and-conquer function MergeTwoGroupLists ($k$ sorted linked lists). The return value of the function is a list containing all nodes from the original $k$ lists and sorted in non-decreasing order.

L1. Function MergeTwoGroupLists ($m$ sorted linked lists) L2. If $m==1$ then return the only list from the input. L3. Divide the input $m$ lists into two groups of lists, with $\lceil m/2 \rceil$ and $\lfloor m/2 \rfloor$ lists, respectively. L4. Recursively call MergeTwoGroupLists for each of these two groups of lists, merging the first group of the lists into one sorted list, $S_1$, and the second group of the lists into one sorted list, $S_2$. L5. Merge the two sorted lists $S_1$ and $S_2$ into one sorted list $S$. L6. Return $S$.

For each of these three algorithms, analyze and give their asymptotic worst-case running times with the big-O notation and in terms of $k$ and $n$.

Note:

• Lower-order terms and constant factors (excluding $k$ and $n$) should be removed in the big-O notation in the answer.
• The bound in the answer needs to be tight.
• Only the final result will be graded and only fully correct answers will be given points. Please clearly mark your final result in the answer sheet.