当前位置: 面试刷题>> 链表插入排序 (经典算法题500道)


题目描述补充

题目:链表插入排序

问题描述: 给定一个单链表的头节点 head,请将链表进行插入排序,使得链表变为升序排列。排序后,链表仍然用原链表中的节点进行表示,不允许申请新的节点空间。

示例

给定链表 4->2->1->3,排序后的链表应该为 1->2->3->4。

PHP 代码示例

<?php

class ListNode {
    public $val;
    public $next;
    
    function __construct($val = 0, $next = null) {
        $this->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 代码示例

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 代码示例

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

码小课网站中有更多相关内容分享给大家学习,包括链表操作的深入解析、其他排序算法的实现等,欢迎大家访问学习。

推荐面试题