# 力扣148——排序链表

## 原题

``````输入: 4->2->1->3

``````输入: -1->5->3->4->0

## 解决

``````Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}``````

### 归并排序

``````public class Solution {
public ListNode sortList(ListNode head) {
// 归并排序

if (head == null || head.next == null) {
}

// 先分隔，利用快慢指针分隔。
ListNode fast = head.next.next;
ListNode slow = head;
while (true) {
if (fast == null || fast.next == null) {
break;
}

fast = fast.next.next;
slow = slow.next;
}
// 后半部分的开头
ListNode second = slow.next;
second = sortList(second);
// 前半部分的开头
slow.next = null;
ListNode first = head;
first = sortList(first);

// 合并
ListNode result = new ListNode(0);
while (first != null && second != null) {
if (first.val < second.val) {
result.next = first;
first = first.next;
} else {
result.next = second;
second = second.next;
}
result = result.next;
}
if (first != null) {
result.next = first;
} else {
result.next = second;
}

}
}``````

### 归并排序——优化

``````public class Solution {
public ListNode sortList(ListNode head) {
// 归并排序
if (head == null || head.next == null) {
}

// 说明只有两个节点
if (head.next.next == null) {
ListNode second = head.next;
if (head.val > second.val) {
} else {
return second;
}
}

// 先分隔，利用快慢指针分隔。
ListNode fast = head;
ListNode slow = head;
while (true) {
if (fast == null || fast.next == null) {
break;
}

fast = fast.next.next;
slow = slow.next;
}
// 后半部分的开头
ListNode second = slow.next;
second = sortList(second);
// 前半部分的开头
slow.next = null;
ListNode first = head;
first = sortList(first);

// 合并
ListNode result = new ListNode(0);
while (first != null && second != null) {
if (first.val < second.val) {
result.next = first;
first = first.next;
} else {
result.next = second;
second = second.next;
}
result = result.next;
}
if (first != null) {
result.next = first;
} else {
result.next = second;
}

}
}``````

### 快速排序

``````class Solution {
public ListNode sortList(ListNode head) {
// 利用快排

// 单个节点是终止节点
if (head == null || head.next == null) {
}
// 比标准值小的节点
ListNode lowHead = new ListNode(0);
ListNode low = lowHead;
// 和标准值一样的节点
ListNode midHead = new ListNode(0);
ListNode mid = midHead;
// 比标准值大的节点
ListNode highHead = new ListNode(0);
ListNode high = highHead;

// 标准值
int val = head.val;
ListNode node = head;
// 遍历
while (node != null) {
// 比标准值大的节点
if (node.val > val) {
high.next = node;
high = high.next;
}
// 比标准值小的节点
else if (node.val < val) {
low.next = node;
low = low.next;
}
// 和标准值一样的节点
else {
mid.next = node;
mid = mid.next;
}
node = node.next;
}
// 终止，避免造成环
low.next = null;
high.next = null;

// 找出小节点链表的末尾
while (low.next != null) {
low = low.next;
}
// 拼接

}
}``````

``当两个链表合并时，如果一个链表已经全部结束，另一个链表剩余的部分可以直接拼接。``

## 总结

https://death00.github.io/