当前位置： 面试刷题>> 在排序链表中插入一个节点 (经典算法题500道)
### 题目描述
给定一个已排序的链表（升序）和一个节点值，请将该节点值插入到链表中，并保持链表的排序特性。如果链表中已经存在该节点值，则不重复插入。
### 示例
假设链表 `1 -> 2 -> 4`，插入值为 `3`，则插入后的链表为 `1 -> 2 -> 3 -> 4`。
如果链表为 `1 -> 2 -> 4`，插入值为 `2`，则链表不变，仍为 `1 -> 2 -> 4`。
### PHP 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课**网站中有更多相关内容分享给大家学习，包括链表操作、算法面试题解析等。