# 148. Sort List

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

Example 1:

``````Input: 4->2->1->3
Output: 1->2->3->4
``````

Example 2:

``````Input: -1->5->3->4->0
Output: -1->0->3->4->5
``````

C++ 解法一：

``````class Solution {
public:
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1);
ListNode *cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
if (l2) cur->next = l2;
return dummy->next;
}
};
``````

Java 解法一：

``````public class Solution {
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
}
public ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if (l1 != null) cur.next = l1;
if (l2 != null) cur.next = l2;
return dummy.next;
}
}
``````

C++ 解法二：

``````class Solution {
public:
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
}
ListNode* merge(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
if (l1->val < l2->val) {
l1->next = merge(l1->next, l2);
return l1;
} else {
l2->next = merge(l1, l2->next);
return l2;
}
}
};
``````

Java 解法二：

``````public class Solution {
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
}
public ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l1, l2.next);
return l2;
}
}
}
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/148

Merge Two Sorted Lists

Sort Colors

Insertion Sort List

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

https://leetcode.com/problems/sort-list/discuss/46857/clean-and-short-merge-sort-solution-in-c

https://leetcode.com/problems/sort-list/discuss/46937/56ms-c-solutions-using-quicksort-with-explanations

https://leetcode.com/problems/sort-list/discuss/46772/i-have-a-pretty-good-mergesort-method-can-anyone-speed-up-the-run-time-or-reduce-the-memory-usage

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation