**Leetcode 148. Sort List

本文主要是介绍**Leetcode 148. Sort List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/sort-list/description/

对链表做nlogn的排序 merge sort大概是最容易写的了吧

之前写的快排，各种Bug 然后再手写merge sort 基本1A

class Solution {
public:int getLen(ListNode *head) {int len = 0;while (head) {len ++;head = head ->next;}return len;}ListNode* splitByPos(ListNode *head, int pos) {ListNode *pre = NULL;while (pos) {pre = head;head = head -> next;pos --;}if (pre) pre->next = NULL;return head;}ListNode* sortList(ListNode* head) {if (!head) return NULL;int len = getLen(head);if (len <= 1) {return head;}int half = len/2;ListNode *head2 = splitByPos(head, half);head = sortList(head);head2 = sortList(head2);ListNode *newHead = NULL;if (head->val < head2->val) {newHead = head;head = head->next;} else {newHead = head2;head2 = head2 -> next;}ListNode *cur = newHead;while (head || head2) {if (!head) {cur->next = head2;head2 = head2 -> next;} else {if (!head2) {cur->next = head;head = head -> next;} else {if (head->val < head2->val) {cur->next = head;head = head->next;} else {cur->next = head2;head2 = head2->next;}}}cur = cur->next;}return newHead;}
};

这篇关于**Leetcode 148. Sort List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---