题目描述补充

题目：向循环有序链表插入节点

给定一个循环有序链表（Circular Sorted Linked List），链表中的节点值按非递减顺序排列，但可能在循环的某处断开，使得链表从尾部链接到头部形成循环。现在需要在链表中找到合适的位置插入一个新的节点，使得链表仍然保持循环且有序。

输入：

• 循环有序链表的头节点 head
• 需要插入的新节点的值 val

输出：

• 插入新节点后的循环有序链表的头节点（如果链表为空，则新节点即为头节点）

注意：

• 链表中的节点值可能重复。
• 如果插入的新值在链表中已存在，则插入到已有值的下一个位置（维持顺序）。

示例代码

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

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

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;
}

码小课分享

码小课网站中有更多关于链表操作的算法题解析和代码示例，包括链表的遍历、反转、合并、查找等经典问题，以及它们在各种编程语言中的实现。这些内容非常适合算法和数据结构的学习者进行实践和提升。