建设银行企业官方网站_邯郸高端网站建设_上海搜索优化推广哪家强_北京网站优化常识

题目：LCR 029

解法一：

特殊情况：

1. 给定链表没有节点，返回新节点
2. 给定链表只有一个节点，将新节点插入，返回给定节点

一般情况：

1. 新节点插入列表中间：当cur小于等于新节点，且next大于等于新节点
2. 新节点插入列表头部：遍历到头尾相连部分时，新节点小于等于头节点，则插入二者之间
3. 新节点插入列表尾部：遍历到头尾相连部分时，新节点大于等于尾节点，则插入二者之间

注意：当cur大于next时，cur为尾节点，next为头节点

    public Node insert(Node head, int insertVal) {Node newNode = new Node(insertVal);if (head == null) {newNode.next = newNode;return newNode;}if (head.next == head) {head.next = newNode;newNode.next = head;return head;}Node cur = head, next = cur.next;while (next != head) {if (cur.val <= insertVal && next.val >= insertVal) break;if (cur.val > next.val && (cur.val <= insertVal || next.val >= insertVal)) {break;}cur = next;next = next.next;}cur.next = newNode;newNode.next = next;return head;}
}