题目描述

给定一个已排序的链表（升序）和一个节点值，请将该节点值插入到链表中，并保持链表的排序特性。如果链表中已经存在该节点值，则不重复插入。

示例

假设链表 1 -> 2 -> 4，插入值为 3，则插入后的链表为 1 -> 2 -> 3 -> 4。

如果链表为 1 -> 2 -> 4，插入值为 2，则链表不变，仍为 1 -> 2 -> 4。

PHP 示例代码

class ListNode {
    public $val;
    public $next;
    
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function insertIntoSortedList($head, $val) {
    $newNode = new ListNode($val);
    
    if ($head === null || $head->val >= $val) {
        $newNode->next = $head;
        return $newNode;
    }
    
    $current = $head;
    while ($current->next !== null && $current->next->val < $val) {
        $current = $current->next;
    }
    
    $current->next = $newNode;
    $newNode->next = $current->next->next;
    
    return $head;
}

// 使用示例
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(4);

$val = 3;
$result = insertIntoSortedList($head, $val);

// 遍历链表打印结果
$current = $result;
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 insertIntoSortedList(head, val):
    new_node = ListNode(val)
    if not head or head.val >= val:
        new_node.next = head
        return new_node
    
    current = head
    while current.next and current.next.val < val:
        current = current.next
    
    new_node.next = current.next
    current.next = new_node
    
    return head

# 使用示例
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(4)

val = 3
result = insertIntoSortedList(head, val)

# 遍历链表打印结果
current = result
while current:
    print(current.val, end=' ')
    current = current.next
# 输出应为：1 2 3 4

JavaScript 示例代码

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function insertIntoSortedList(head, val) {
    const newNode = new ListNode(val);
    if (!head || head.val >= val) {
        newNode.next = head;
        return newNode;
    }
    
    let current = head;
    while (current.next && current.next.val < val) {
        current = current.next;
    }
    
    newNode.next = current.next;
    current.next = newNode;
    
    return head;
}

// 使用示例
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(4);

const val = 3;
const result = insertIntoSortedList(head, val);

// 遍历链表打印结果
let current = result;
while (current) {
    console.log(current.val);
    current = current.next;
}
// 输出应为：1 2 3 4

码小课网站中有更多相关内容分享给大家学习，包括链表操作、算法面试题解析等。