以下代码是链表排序代码,请问它们是根据什么信息(什么内容)进行排序的?
Q3 链表排序
1 double cmp(ListNode *p ,ListNode *q)
2 {return (p->keyVal - q->keyVal);}
3
4 ListNode* mergeSortList(ListNode *head)
5 {
6 ListNode *p, *q, *tail, *e;
7 int nstep = 1;
8 int nmerges = 0;
9 int i;
10 int psize, qsize;
11 if (head == NULL || head->next == NULL)
12 {return head;}
13 while (1)
14 { p = head;
15 tail = NULL;
16 nmerges = 0;
17 while (p)
18 { nmerges++; q = p; psize = 0;
19 for (i = 0; i < nstep; i++)
{
20 psize++;
21 q = q->next;
22 if (q == NULL)break;
23 }
24 qsize = nstep;
25 while (psize >0 || (qsize >0 && q))
26 {
27 if (psize == 0)
{
e = q; q = q->next; qsize--;
}
28 else
if (q == NULL || qsize == 0)
{
e = p; p = p->next; psize--;
}
29 else
if (cmp(p,q) <= 0)
{
e = p; p = p->next; psize--;
}
30 else
{
e = q; q = q->next; qsize--;
}
31 if (tail != NULL)
{
tail->next = e;
}
32 else{head = e;}