本文共 3546 字，大约阅读时间需要 11 分钟。

Sort a linked list in O(n log n) time using constant space complexity.

分析：

题目要求对链表进行排序，如果采用插入、冒泡等排序方式，则时间复杂度将是O（n*n），达不到题目要求的O（n log n）的要求。O（n log n）复杂度的有快排和归并排序，对于链表来说，归并排序更适合一点。这样题目转换为将一个链表拆分成两个有序的链表，然后再进行归并排序。关键就在于链表中点的获取。对于链表中点获取可以采取快慢指针法，快指针每次进2步，慢指针每次一步，这样快指针到达终点时，慢指针将处于链表中点处。

代码如下，执行时间约 68ms：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:		ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {			ListNode* head =NULL, *tmp;			while (l1 && l2)			{				if (l1->val <= l2->val)				{					if (!head)					{						head = l1;						tmp = head;					}else{						tmp ->next= l1;						tmp = tmp->next;					}					l1 = l1->next;				}else{					if (!head)					{						head = l2;						tmp = head;					} 					else					{						tmp ->next = l2;						tmp = tmp->next;					}					l2 = l2->next;				}			}			if (l1)			{				tmp->next = l1;			}			if (l2)			{				tmp->next = l2;			}			return head;		}    ListNode *sortList(ListNode *head) {        ListNode tmpNode = ListNode(INT_MIN);		if (head==NULL || head->next==NULL)			{				return head;			}			ListNode *p1=head, *p2=head->next;			while (p2 && p2->next)			{				p1 = p1->next;				p2 =p2->next->next;			}			p2 = p1->next;			p1->next= NULL;			return mergeTwoLists(sortList(head), sortList(p2));    }};

2018-11-12:补充

上述方法虽满足了O（nlogn）的时间和O（1）的空间复杂度，但通过快慢指针方法找链表中点，需要首先遍历链表，浪费了很多操作。下面这种方法也是归并排序，但不需要扫描链表获得链表中点、也不递归。在实现上比之前的快很多。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */static struct ListNode *merge(struct ListNode*a, struct ListNode*b) {	struct ListNode head, *tail;	tail = &head;	while (a && b) {		if ((a->val <= b->val) ) {			tail->next = a;			a = a->next;		} else {			tail->next = b;			b = b->next;		}		tail = tail->next;	}	tail->next = a ? : b;	return head.next;}#define MAX_LIST_LENGTH_BITS 31struct ListNode* sortList(struct ListNode* head) {    struct ListNode *part[MAX_LIST_LENGTH_BITS + 1];	int lev;	int max_lev = 0;	struct ListNode *bnode;	if (head == NULL || head->next==NULL)		return head;	memset(part, 0, sizeof(part));	bnode = head;	while (bnode) {		struct ListNode *cur = bnode;		bnode = bnode->next;		cur->next = NULL;		for (lev = 0; part[lev]; lev++) {			cur = merge(part[lev], cur);			part[lev] = NULL;		}		if (lev > max_lev) {			if ((lev >= MAX_LIST_LENGTH_BITS)) {				lev--;			}			max_lev = lev;		}		part[lev] = cur;	}	for (lev = 0; lev < max_lev; lev++)		if (part[lev])			bnode = merge(part[lev], bnode);	bnode = merge(part[max_lev], bnode);	return bnode;}

与之类似的还有

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* sortList(struct ListNode* head) {	struct ListNode *p, *q, *e, **tail;	int k, psize, qsize;	if (!head)		return 0;	int count = 0;	struct ListNode *pHead = head;	p = pHead;	while (p) {		count++;		p = p->next;	}	for (k = 1; k < count; k *= 2) {		tail = &pHead;		for (p = q = pHead; p; p = q) {			/* step 'k' places from p; */			for (psize = 0; q && psize < k; psize++)				q = q->next;			qsize = k;			/* two lists, merge them. */			while (psize || (qsize && q)) {				/* merge the next element */				if (psize == 0 || ((qsize && q) && ((p->val - q->val) >= 0))) {					/* p is empty, or p > q, so q next */					e = q;					q = q->next;					qsize--;				} else {					e = p;					p = p->next;					psize--;				}				e->next = NULL; /* break accidental loops. */				*tail = e;				tail = &e->next;			}		}	}	return pHead;}

转载地址：http://zfxti.baihongyu.com/