共计 6477 个字符，预计需要花费 17 分钟才能阅读完成。
148. 排序链表
1. 题目形容
在 O(n log n) 工夫复杂度和常数级空间复杂度下，对链表进行排序
2. 解题报告
针对 nlogn 的排序算法，次要有疾速排序，归并排序和堆排序。其中，堆排序利用了数组的间断个性。所以这里不能采纳。其次，在疾速排序中，设计大量数字的替换且单链表因为只能单向遍历，应用 partition 不是很直观。
所以，本题采纳归并排序链表版来实现。
具体思路如下：
1. 应用快慢指针，找到链表的中点。
2. 对链表的前半部分和后半局部别离排序。
3. 将两局部合并。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {return sortList(head, NULL);
}
private:
// sort [beg, end), and return new head, and tail->next = end;
ListNode* sortList(ListNode*beg, ListNode* end) {if (beg == end || !beg || beg->next == end) {return beg;}
// at least has two node
// [head, mid, end], maybe head == mid == end
// [head, mid) < mid < [mid->next, end)
ListNode* head = NULL; // new head
ListNode* mid = NULL;
beg = partition(beg, end, &head, &mid);
// sort [mid->next, end)
if (mid && mid->next != end) {mid->next = sortList(mid->next, end);
}
// sort [head, mid)
return sortList(head, mid);
}
ListNode* partition(ListNode* beg, ListNode* end,
ListNode** p_head, ListNode** p_mid) {if (!beg || !p_head || !p_mid) {return beg;}
ListNode* mid = beg;
ListNode* tail1 = NULL;
ListNode* tail2 = NULL;
int v = mid->val;
ListNode* p = mid->next;
while (p != end) {if (p->val < v) {if (!*p_head) {
*p_head = p;
tail1 = p;
} else {
tail1->next = p;
tail1 = p;
}
} else {if (!tail2) {
mid->next = p;
tail2 = p;
} else {
tail2->next = p;
tail2 = p;
}
}
p = p->next;
}
if (tail1) {tail1->next = mid;}
else {*p_head = mid;}
if (tail2) {tail2->next = end;}
else {mid->next = end;}
*p_mid = mid;
return *p_head;
}
};3. 最佳答案
c 答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//head 不参加排序！void mergeSortList(struct ListNode* head) {
struct ListNode* slow, *fast,*pre;
if (NULL == head)
return; // 有效输出
else{
struct ListNode R;
slow = fast = head;
do {if ((fast = fast->next) != NULL) {
fast = fast->next;
slow = slow->next;
}
} while (fast);
if (NULL == slow->next)return; // 只有 0 或 1 个元素
R.next = slow->next;
slow->next = NULL; // 一分为二
mergeSortList(head); // 使左半有序
mergeSortList(&R); // 使右半有序
slow = head->next; fast = R.next; // 两边筹备进行归并
}
pre = head; // 尾插法（是 slow 的前驱）do {if (fast->val < slow->val) { // 左边比右边小
pre = pre->next = fast; // 原 pre->next==slow，所以不会丢链
fast = fast->next;
pre->next = slow; // 还原 pre 是 slow 的前驱
if (fast == NULL)
break; // 右边的 pre 原本就接着 slow，无需解决
}
else { // 右边小
pre = slow;
slow = slow->next;
if (slow == NULL) {
pre->next = fast; // 残余的左边接到右边
break;
}
}
} while (true);
}
struct ListNode* sortList(struct ListNode* head) {
struct ListNode Head; Head.next = head; // 真正头结点，不参加排序
mergeSortList(&Head);
return Head.next;
}
c++ 答案
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode * merge(ListNode* left, ListNode* right)
{
ListNode* newhead = NULL, *pre=NULL;
while (left && right)
{if (left->val < right->val)
{if (!newhead)
{
newhead = pre = left;
left = left->next;
}
else
{
pre->next = left;
pre = pre->next;
left = left->next;
}
}
else
{if (!newhead)
{
newhead = pre = right;
right = right->next;
}
else
{
pre->next = right;
pre = pre->next;
right = right->next;
}
}
}
while (left)
{
pre->next = left;
left = left->next;
pre = pre->next;
}
while (right)
{
pre->next = right;
right = right->next;
pre = pre->next;
}
pre->next = NULL;
return newhead;
}
ListNode* sortList(ListNode* head) {if (head == NULL || head->next == NULL)
return head;
else
{
ListNode* slow = head, *fast = head->next;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* temp = slow->next;
slow->next = NULL;
ListNode* l = sortList(head);
ListNode* r = sortList(temp);
return merge(l, r);
}
}
};
java 答案
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
// 快慢指针寻找链表的两头节点
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 把链表分为两段
ListNode l1 = head;
ListNode l2 = slow.next;
slow.next = null;
// Merge Sort
l1 = sortList(l1);
l2 = sortList(l2);
return merge(l1, l2);
}
// 归并两个曾经排好序的链表
private ListNode merge(ListNode l1, ListNode l2) {if (l1 == null) return l2;
if (l2 == null) return l1;
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;
else cur.next = l2;
return dummy.next;
}
}
JavaScript 答案
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var merge = function(l1,l2) {var l = new ListNode();
var p = l;
while(l1 && l2) {if(l1.val < l2.val) {
p.next = l1;
l1 = l1.next
} else {
p.next = l2;
l2 = l2.next
}
p = p.next
}
if(l1) {p.next = l1;}
if(l2) {p.next = l2;}
return l.next;
}
var sortList = function(head) {if(head === null || head.next === null) {return head;}
var slow = head;
var fast = head;
var prev = null;
while(fast && fast.next) {
prev = slow
fast = fast.next.next;
slow = slow.next
}
prev.next = null;
return merge(sortList(head), sortList(slow));
};
c# 答案
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {val = x;}
* }
*/
public class Solution {public ListNode SortList(ListNode head) {if(head == null) return head;
ListNode now = head;
List<int> list = new List<int>();
while(now != null)
{list.Add(now.val);
now = now.next;
}
list.Sort();
int length = list.Count;
ListNode result = new ListNode(list[0]);
now = result;
for(int i=1;i<length;i++)
{now.next = new ListNode(list[i]);
now = now.next;
}
return result;
}
}
python2.x 答案
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
node = head
res=[]
while node:
res.append(node.val)
node = node.next
res.sort()
if not res:
return None
newhead = ListNode(res[0])
cur_Node = newhead
for i,v in enumerate(res):
if i == 0:
continue
obj = ListNode(v)
cur_Node.next=obj
cur_Node=obj
return newhead
python3.x 答案
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head: return None
res = []
while head:
res.append(head)
head = head.next
res.sort(key = lambda ele: ele.val)
temp = res[0]
for i in range(1,len(res)):
temp.next = res[i]
temp = res[i]
res[-1].next = None
return res[0]
go 答案
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {return head}
middle := split(head)
return merge(sortList(head), sortList(middle))
}
// 双指针切分 list
func split(head *ListNode) *ListNode {
slow, fast := head, head
var tail *ListNode
for fast != nil && fast.Next != nil {
tail = slow
slow = slow.Next
fast = fast.Next.Next
}
tail.Next = nil
return slow
}
func merge(left ,right *ListNode) *ListNode {
var head, cur, pre *ListNode
for left != nil && right != nil {
if left.Val < right.Val {
cur = left
left = left.Next
} else {
cur = right
right = right.Next
}
// 生成 head
if head == nil {head = cur} else {pre.Next = cur}
pre = cur
}
if left == nil {pre.Next = right} else {pre.Next = left}
return head
}
正文完
