当前位置： 面试刷题>> 排序链表(经典算法150题)
### 题目描述
给定一个单链表的头节点 `head`，请编写一个函数对链表进行排序。排序时，要求只能使用常数级额外空间，也就是说，你不能使用除链表本身以外的其他数据结构来辅助排序。
**注意**：
- 链表的长度在范围 `[0, 5 * 10^4]` 内。
- `-10^5 <= Node.val <= 10^5`
### 示例
假设链表是 `1 -> 4 -> 2 -> 8 -> 3`，排序后应为 `1 -> 2 -> 3 -> 4 -> 8`。
### 解题思路
由于题目要求只能使用常数级额外空间，我们不能使用归并排序（虽然归并排序对链表排序效率很高，但空间复杂度为 O(n)）。这里我们可以采用**自底向上的归并排序**（也称为迭代归并排序），每次将链表分割成更小的部分，然后使用归并的思想将相邻的已排序部分合并起来。
### PHP 示例代码
```php
val = $val;
$this->next = $next;
}
}
function sortList($head) {
if ($head == null || $head->next == null) {
return $head;
}
$dummy = new ListNode(0);
$dummy->next = $head;
$subLength = 1;
while ($subLength < floor(countNodes($head) / 2) + 1) {
$prev = $dummy;
$curr = $dummy->next;
while ($curr != null && $curr->next != null) {
$head1 = $curr;
$tail1 = splitList($head1, $subLength);
$head2 = $tail1->next;
$tail2 = splitList($head2, $subLength);
$merged = mergeLists($head1, $head2);
$prev->next = $merged;
while ($prev->next != $tail2) {
$prev = $prev->next;
}
$curr = $tail2;
}
$subLength *= 2;
}
return $dummy->next;
}
function countNodes($head) {
$count = 0;
while ($head != null) {
$count++;
$head = $head->next;
}
return $count;
}
function splitList($head, $n) {
$prev = null;
$count = 0;
while ($head != null && $count < $n - 1) {
$prev = $head;
$head = $head->next;
$count++;
}
if ($prev != null) {
$prev->next = null;
}
return $head;
}
function mergeLists($l1, $l2) {
$dummy = new ListNode(0);
$tail = $dummy;
while ($l1 != null && $l2 != null) {
if ($l1->val < $l2->val) {
$tail->next = $l1;
$l1 = $l1->next;
} else {
$tail->next = $l2;
$l2 = $l2->next;
}
$tail = $tail->next;
}
if ($l1 != null) {
$tail->next = $l1;
}
if ($l2 != null) {
$tail->next = $l2;
}
return $dummy->next;
}
?>
```
### Python 示例代码
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
sub_length = 1
while sub_length < len(list(to_list(head))) // 2 + 1:
prev = dummy
curr = dummy.next
while curr and curr.next:
head1 = curr
tail1 = split_list(head1, sub_length)
head2 = tail1.next
tail2 = split_list(head2, sub_length)
merged = merge_lists(head1, head2)
prev.next = merged
while prev.next != tail2:
prev = prev.next
curr = tail2
sub_length *= 2
return dummy.next
def to_list(node):
return [node.val for node in iter(lambda n=node: n if n else None, None)]
def len_list(node):
length = 0
while node:
length += 1
node = node.next
return length
def split_list(head, n):
prev = None
for _ in range(n - 1):
prev = head
head = head.next
if prev:
prev.next = None
return head
def merge_lists(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 is not None else l2
return dummy.next
```
### JavaScript 示例代码
```javascript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function sortList(head) {
if (!head || !head.next) return head;
let dummy = new ListNode(0);
dummy.next = head;
let subLength = 1;
while (subLength < Math.floor(countNodes(head) / 2) + 1) {
let prev = dummy;
let curr = dummy.next;
while (curr && curr.next) {
let head1 = curr;
let tail1 = splitList(head1, subLength);
let head2 = tail1.next;
let tail2 = splitList(head2, subLength);
let merged = mergeLists(head1, head2);
prev.next = merged;
while (prev.next !== tail2) {
prev = prev.next;
}
curr = tail2;
}
subLength *= 2;
}
return dummy.next;
}
function countNodes(head) {
let count = 0;
while (head) {
count++;
head = head.next;
}
return count;
}
function splitList(head, n) {
let prev = null;
for (let i = 0; i < n - 1 && head; i++) {
prev = head;
head = head.next;
}
if (prev) prev.next = null;
return head;
}
function mergeLists(l1, l2) {
let dummy = new ListNode(0);
let tail = dummy;
while (l1 && l2) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 ? l1 : l2;
return dummy.next;
}
```
以上代码展示了如何在 PHP、Python 和 JavaScript 中使用自底向上的归并排序算法对链表进行排序，满足了题目要求的常数级额外空间。