首页 > 代码库 > LeetCode:Sort List
LeetCode:Sort List
Problem:
Sort a linked list in O(n log n) time using constant space complexity.
解题思路:
首先,时间复杂度能达到O(nlgn)的排序算法,常见的有3种:堆排序、归并排序和快速排序,
而对于链表,用堆排序显然不太可能,所以,我们可用归并或者是快排.由于合并两个链表,只用
修改相应的指针,所以其能做到空间复杂度O(1).下面是利用归并排序思想实现的链表排序.
解题思路:
class Solution { public: ListNode *sortList(ListNode *p) { if (p == NULL || p->next == NULL) return p; //加入一个头节点,避免合并时讨论rear为空的情况. ListNode *head = new ListNode(-1), *q = head; head->next = p; int cnt = 0; while (p) { ++cnt; p = p->next; if (cnt % 2 == 0) q = q->next; } p = q->next, q->next = NULL; //递归进行左右两支排序 head->next = q = sortList(head->next); p = sortList(p); //合并 q = Merge(head, p); free(head); return q; } ListNode* Merge(ListNode *head, ListNode *r) { ListNode *l = head->next, *rear = head; while (l && r) { if (l->val < r->val) { rear->next = l; l = l->next, rear = rear->next; } else { rear->next = r; r = r->next, rear = rear->next; } } while (l) { rear->next = l; l = l->next, rear = rear->next; } while (r) { rear->next = r; r = r->next, rear = rear->next; } return head->next; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。