【题目】
一个环形单链表从头节点head开始不降序，同时由最后的节点指回头节点。给定一个环形单链表的头节点head和一个整数num，请生成节点值为num的新节点，并插入到这个环形链表中，保证调整后的链表依然有序。
【解答】
package zcy;public class P87_insertNewNode {public static void main(String[] args) {Node head = new Node(2);Node root = head;Node node1 = new Node(3);Node node2 = new Node(4);Node node3 = new Node(5);Node node4 = new Node(6);Node node5 = new Node(7);root.next = node1;root = root.next;root.next = node2;root = root.next;root.next = node3;root = root.next;root.next = node4;root = root.next;node5.next = head;root.next = node5;Node newHead = insertNewNode(head, new Node(1));root = newHead;while (root != null) {System.out.println(root.value);if (root.next == newHead) {break;}root = root.next;}}public static Node insertNewNode(Node head, Node node) {if (node == null) {return head;}if (head == null) {node.next = node;return node;}Node pre = head;Node cur = pre.next;while (cur != head) {if (pre.value < node.value && node.value <= cur.value) {break;}pre = cur;cur = cur.next;}//跳出循环有两种可能：1、在中间找到了位置，2、遍历完了都找不到地方插入。//若找不到地方插入，有两种可能：num最小或者最大，直接放在head前面即可（这个时候cur=head）pre.next = node;node.next = cur;return head.value < node.value ? head : node; //若新增节点是最小，以它作为头节点返回}public static class Node {public int value;public Node next;public Node(int value) {this.value = value;}}
}