第二章 链表问题（向有序的环形单链表中插入新节点）

【题目】

        一个环形单链表从头节点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;
        }
    }
}