資料結構與演算法

(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}, \dots, a_{i,n}$. Each of the $k$ lists has the numbers sorted in non-decreasing order, i.e., $a_{i,1} \le a_{i,2} \le \dots \le a_{i,n}$. 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. For each of these three algorithms, analyze and give their asymptotic worst-case running times with big-O notation and in terms of $k$ and $n$ (tight bound; drop lower-order terms and constant factors other than $k$ and $n$).

• Student A: Repeatedly iterate over the numbers in the head nodes of the $k$ lists, find the node $M$ with the smallest number, remove $M$ from its original list and append it to the tail of result list $S$; until all $k$ lists are empty.
• Student B: Create an empty min heap $H$. Remove the $k$ head nodes and insert them into $H$ (each node also carries the index of its source list). Repeatedly remove the min node $M$ from $H$, append it to $S$, and (if its source list $m$ is not empty) remove the head of list $m$ and insert into $H$; while $H$ is not empty.
• Student C: Recursive divide-and-conquer MergeTwoGroupLists: if only one list, return it; otherwise split the $m$ input lists into two groups of $\lceil m/2 \rceil$ and $\lfloor m/2 \rfloor$ lists, recursively merge each group into one sorted list $S_1, S_2$, then merge the two sorted lists $S_1, S_2$ into one.