当前位置： 面试刷题>> 向循环有序链表插入节点 (经典算法题500道)
### 题目描述补充
题目：向循环有序链表插入节点
给定一个循环有序链表（Circular Sorted Linked List），链表中的节点值按非递减顺序排列，但可能在循环的某处断开，使得链表从尾部链接到头部形成循环。现在需要在链表中找到合适的位置插入一个新的节点，使得链表仍然保持循环且有序。
**输入**：
- 循环有序链表的头节点 `head`
- 需要插入的新节点的值 `val`
**输出**：
- 插入新节点后的循环有序链表的头节点（如果链表为空，则新节点即为头节点）
**注意**：
- 链表中的节点值可能重复。
- 如果插入的新值在链表中已存在，则插入到已有值的下一个位置（维持顺序）。
### 示例代码
#### PHP 示例
```php
class ListNode {
public $val;
public $next;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
function insertIntoCircularSortedList($head, $val) {
if ($head == null) {
return new ListNode($val);
}
$newNode = new ListNode($val);
$tail = $head;
$isInserted = false;
do {
if ($tail->next == $head && $tail->val <= $val) {
// 插入到头部
$newNode->next = $head;
$head = $newNode;
$isInserted = true;
break;
}
if ($tail->next->val >= $val && ($tail->next != $head || $tail->val <= $val)) {
// 找到插入位置
$newNode->next = $tail->next;
$tail->next = $newNode;
$isInserted = true;
break;
}
$tail = $tail->next;
} while ($tail != $head);
if (!$isInserted) {
// 插入到尾部
$tail->next = $newNode;
$newNode->next = $head;
}
return $head;
}
```
#### Python 示例
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertIntoCircularSortedList(head, val):
if not head:
return ListNode(val)
newNode = ListNode(val)
tail = head
inserted = False
while True:
if tail.next == head and tail.val <= val:
# 插入到头部
newNode.next = head
head = newNode
inserted = True
break
if tail.next.val >= val and (tail.next != head or tail.val <= val):
# 找到插入位置
newNode.next = tail.next
tail.next = newNode
inserted = True
break
tail = tail.next
if tail == head:
break
if not inserted:
# 插入到尾部
tail.next = newNode
newNode.next = head
return head
```
#### JavaScript 示例
```javascript
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function insertIntoCircularSortedList(head, val) {
if (!head) {
return new ListNode(val);
}
const newNode = new ListNode(val);
let tail = head;
let inserted = false;
do {
if (tail.next === head && tail.val <= val) {
// 插入到头部
newNode.next = head;
head = newNode;
inserted = true;
break;
}
if (tail.next.val >= val && (tail.next !== head || tail.val <= val)) {
// 找到插入位置
newNode.next = tail.next;
tail.next = newNode;
inserted = true;
break;
}
tail = tail.next;
} while (tail !== head);
if (!inserted) {
// 插入到尾部
tail.next = newNode;
newNode.next = head;
}
return head;
}
```
### 码小课分享
码小课网站中有更多关于链表操作的算法题解析和代码示例，包括链表的遍历、反转、合并、查找等经典问题，以及它们在各种编程语言中的实现。这些内容非常适合算法和数据结构的学习者进行实践和提升。