当前位置： 面试刷题>> 链表插入排序 (经典算法题500道)
### 题目描述补充
题目：链表插入排序
**问题描述**：
给定一个单链表的头节点 `head`，请将链表进行插入排序，使得链表变为升序排列。排序后，链表仍然用原链表中的节点进行表示，不允许申请新的节点空间。
**示例**：
给定链表 4->2->1->3，排序后的链表应该为 1->2->3->4。
### PHP 代码示例
```php
val = $val;
$this->next = $next;
}
}
function insertionSortList($head) {
if ($head == null || $head->next == null) {
return $head;
}
$dummy = new ListNode(0); // 创建一个哑节点
$current = $head;
$tail = $dummy;
while ($current != null) {
$nextTemp = $current->next; // 保存当前节点的下一个节点
// 插入到已排序链表中
$prev = $dummy;
while ($prev->next != null && $prev->next->val < $current->val) {
$prev = $prev->next;
}
$current->next = $prev->next; // 插入操作
$prev->next = $current;
$tail = $tail->next ?? $tail; // 更新尾节点，如果尾节点未更新，则保持原样
$current = $nextTemp; // 移动到下一个节点
}
return $dummy->next;
}
// 示例用法
$head = new ListNode(4);
$head->next = new ListNode(2);
$head->next->next = new ListNode(1);
$head->next->next->next = new ListNode(3);
$sortedHead = insertionSortList($head);
// 打印排序后的链表
$current = $sortedHead;
while ($current != null) {
echo $current->val . " ";
$current = $current->next;
}
// 输出: 1 2 3 4
?>
```
### Python 代码示例
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertionSortList(head):
if not head or not head.next:
return head
dummy = ListNode(0)
current = head
tail = dummy
while current:
next_temp = current.next
prev = dummy
while prev.next and prev.nextval. < current.val:
prev = prev.next
current.next = prev.next
prev.next = current
tail = tail.next if tail.next else tail
current = next_temp
return dummy.next
# 示例用法
head = ListNode(4)
head.next = ListNode(2)
head.next.next = ListNode(1)
head.next.next.next = ListNode(3)
sorted_head = insertionSortList(head)
# 打印排序后的链表
current = sorted_head
while current:
print(current.val, end=' ')
current = current.next
# 输出: 1 2 3 4
```
### JavaScript 代码示例
```javascript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val);
this.next = (next===undefined ? null : next);
}
function insertionSortList(head) {
if (!head || !head.next) return head;
let dummy = new ListNode(0);
let current = head;
let tail = dummy;
while (current) {
let nextTemp = current.next;
let prev = dummy;
while (prev.next && prev.next.val < current.val) {
prev = prev.next;
}
current.next = prev.next;
prev.next = current;
tail = tail.next || tail;
current = nextTemp;
}
return dummy.next;
}
// 示例用法
let head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);
let sortedHead = insertionSortList(head);
// 打印排序后的链表
let current = sortedHead;
while (current) {
console.log(current.val);
current = current.next;
}
// 输出: 1 2 3 4
```
码小课网站中有更多相关内容分享给大家学习，包括链表操作的深入解析、其他排序算法的实现等，欢迎大家访问学习。