向有序的环形单链表中插入新节点

遍历单向循环链表，找到待插入节点的正确位置即可，核心是完成insertNode方法：

(1) 如果头结点的值大于待插入节点，就直接遍历到尾节点，使尾节点指向待插入节点，待插入节点指向之前的头结点。返回待插入节点作为新链表的头结点。

(2) 非(1)的情况先向后遍历，遇到当前节点的下一个节点的值大于等于待插入节点的值，就将待插入节点插入在当前节点之后；如果直到尾节点还没有遇到下一个节点的值大于等于待插入节点的情况，就和(1)的情况相同，只是返回的仍然是原来的头结点。

注：通过题中所给的链表长度来判断是否到达链表的尾节点。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    public int val;
    public ListNode next;
    
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] elems = br.readLine().trim().split(" ");
        // 构建单向循环链表
        ListNode head = new ListNode(Integer.parseInt(elems[0]));
        ListNode cur = head;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(elems[i]));
            cur = cur.next;
        }
        cur.next = head;
        // 插入节点
        int target = Integer.parseInt(br.readLine().trim());
        head = insertNode(head, target, n);
        // 遍历插入节点后的链表
        int cursor = 0;
        while(cursor < n + 1){
            System.out.print(head.val + " ");
            head = head.next;
            cursor ++;
        }
    }
    
    private static ListNode insertNode(ListNode head, int target, int len) {
        ListNode cur = head;
        int cursor = 0;
        if(cur.val >= target){
            // 如果头结点的值就比target大，就遍历到尾节点，改变尾节点指针的指向
            while(cursor < len - 1){
                cur = cur.next;
                cursor ++;
            }
            ListNode node = new ListNode(target);
            cur.next = node;
            node.next = head;
            return node;
        }else{
            // 否则将target插入到合适的中间位置(也有可能是最后一个位置)
            while(cur.next.val < target && cursor < len - 1){
                cur = cur.next;
                cursor ++;
            }
            ListNode temp = cur.next;
            ListNode node = new ListNode(target);
            node.next = temp;
            cur.next = node;
            return head;
        }
    }
}

此题测试用例情况考虑不周全，比如 环形链表只有一个节点的情况、头节点比插入值要大的情况。下面是考虑比较完整的代码：

list_node * insert_num(list_node * head, int num)
{
    //////在下面完成代码
    list_node* node = new list_node;
    node->val = num;
    if(head==nullptr) { //空链表情况
        node->next = node;
        return node;
    }
    list_node* p=head;
    if(head->val>num) { //头节点比插入值大的情况，需要把插入值作为新的头  while(p->next != head) p=p->next;
        p->next = node; 
        node->next = head;
        return node;
    }
    if(head->next == head) {
        head->next = node;
        node->next = head;
        return head;
    }
    list_node* preNode = head;
    p = p->next;
    while(p!=head) {
        list_node* curNode=p;
        p = p->next;
        if(curNode->val <num) {
            preNode = curNode;
            continue;
        }
        preNode->next = node;
        node->next = curNode;
        break;
    }
    return head;
}

书上的代码如下：（更简洁）

list_node * insert_num(list_node * head, int num)
{
    //////在下面完成代码
    
    list_node* node = new list_node;
    node->val = num;
    if(head==nullptr) {
        node->next = node;
        return node;
    }
    list_node* pre = head;
    list_node* cur = head->next;
    while(cur!=head) {
        if(pre->val <= num && cur->val >=num) break;
        pre = cur;
        cur = cur->next;
    }
    pre->next = node;
    node->next = cur;
    return head->val<num?head:node;
}

第19个用例为什么没有第三行输入，我这个结果集有省略号，各位能帮我看看么
import java.io.*;
class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
        this.next = null;
    }
}
public class Main{
    public static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        int insertNodeValue = Integer.parseInt(bufferedReader.readLine());
        ListNode a = null;
        ListNode k= null;
        n = numbers.length;
        for(int i = 0; i < n;i++){
            if(a!=null){
                a.next = new ListNode(Integer.parseInt(numbers[i]));
                a = a.next;
            }else{
                a = new ListNode(Integer.parseInt(numbers[i]));
                k = a;
            }
        }
        a.next = k;
        a = k;
        if(insertNodeValue(a,n,insertNodeValue)){
            a = sort(a);
        }else{
            a = k;
        }
        StringBuffer sb = new StringBuffer();
        int newLen = n+1;
        while(newLen-->0){
//             System.out.print(a.val+" ");
            sb.append(a.val).append(" ");
            a = a.next;

        }
        System.out.print(sb);
    }
    
   public static boolean insertNodeValue(ListNode listNode,int len,int value){
        ListNode v = new ListNode(value);
        boolean bool = false;
        for(int i =0;i < len;i++){
            if(listNode.val<value&&(listNode.next.val>value||i==len-1)){
                v.next = listNode.next;
                listNode.next = v;
                break;
            }else if(i==0&&listNode.val>value){
                while(len>0){
                    if(len--==1){
                        v.next = listNode.next;
                        listNode.next = v;
                        bool = true;
                        break;
                    }else{
                        listNode = listNode.next;
                    }
                }
            }
            listNode = listNode.next;
        }
        return bool;
    }
    
    public static ListNode sort(ListNode listNode){
        while(true){
            if(listNode.next.val<listNode.val){
                listNode = listNode.next;
                break;
            }else{
                listNode = listNode.next;
            }
        }
        return listNode;
    }
}

#列表元素个数
n=int(input())
#列表元素
number_list=list(map(int,input().split()))
#要插入的元素
num=int(input())
number_list.append(num)
#排序
number_list.sort()
#输出
print(' '.join(map(str,number_list)))

map(元素类型，可迭代对象）：将一个可迭代对象中的每个元素的元素类型修改为指定的元素类型

所以map(str,number_list),map(int,input().split())都是在修改元素类型

input().split():将读取到的字符串按照空格进行分割

append():用于在一个列表后面添加一个元素

注意是不降序，因此需要判断相等的情况。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static Node insert(Node head, int num) {
        Node node = new Node(num);
        if (head == null) {
            node.next = node;
            return node;
        }
        Node pre = head;
        Node cur = head.next;
        while (cur != head) {
            if (pre.value <= num && cur.value >= num) {
                break;
            }
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = node;
        node.next = cur;
        return head.value < node.value ? head : node;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        int num = Integer.parseInt(bufferedReader.readLine());
        Node head = listGenerator(n, numbers);
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = head;
        head = insert(head, num);
        System.out.print(head.value + " ");
        node = head.next;
        while (node != head) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }
}

list_node * getlastnode(list_node * root)
{
    list_node * p = root;
    while(p->next !=root)
        p = p->next;
    return p;
}


list_node * insert_num(list_node * head, int num)
{
    //////在下面完成代码
    //插入是正常插入
    list_node * pnode = new list_node();
    pnode->val=num;
    //保存头节点
    list_node * phead = head;
    //还需要考虑头节点比要插入的节点大的情况，看了别的代码才想起来，这脑子
    list_node * pre = getlastnode(head);
    if(head->val>=num)
    {
        pre->next = pnode;
        pnode->next=head;
        return pnode;
    }
    //开始遍历
    while(phead->val<num)
    {
        pre = phead;
        phead = phead->next;
        if(phead == head)
            break;
    }
    //这时候就可以直接插入
    pre->next = pnode;
    pnode->next =phead;
    return head;
}

需要考虑的情况其实不多，主要是漏了头节点的值比要插入的节点的值大的情况，所以需要先找到环形单链表的尾节点；

后面在正常向环形链表里插入的时候需要注意，while判定退出的条件是当前节点的值大于num，所以还需要保存当前节点的上一个节点。