如果把这题看做是Merge Two Sorted Lists的简单扩展,那么就大错特错了,至少程序在运行时间上就十分不理想。做一个简单分析,假设单链表数组数目为n,每一个的节点数目分别为l_0, l_1, l_2, ..., l_{n-1},首先合并lists[0]和lists[1]得到一个新的listTmp,再依次用listTmp去合并lists[2], lists[3], ..., lists[n-1],那么所做的这n-1次合并,在最坏的情况下(不妨先假设l_1, l_2, ...的长度相同,便于下述的说明),需要扫描的节点数目分别是l_0, l_0 + l_1, l_0 + l_1 + l_2, ..., l_0 + l_1 + ... + l_{n-2},因此在nl_i, i = 0, ..., n - 1都比较大的时候,这种做法是不可取的。

有一个简单的优化,就是借助归并排序的思想,实质是分治。在写法上可以进一步优化,折半合并..个人对这段程序比较满意。