面试算法29：排序的循环链表

问题

在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保证插入节点之后的循环链表仍然是排序的。

分析

首先分析在排序的循环链表中插入节点的规律。当在图4.15（a）的链表中插入值为4的节点时，新的节点位于值为3的节点和值为5的节点之间。这很容易理解，为了使插入新节点的循环链表仍然是排序的，新节点的前一个节点的值应该比新节点的值小，后一个节点的值应该比新节点的值大。

但是特殊情况需要特殊处理。如果新节点的值比链表中已有的最大值还要大，那么新的节点将被插入最大值和最小值之间。如果新节点的值比链表中已有的最大值还要大，那么新的节点将被插入最大值和最小值之间。

在上面的规则中，总是先试图从链表中找到符合条件的相邻的两个节点。如果开始的时候链表中的节点数小于2，那么应该有两种可能。第1种可能是开始的时候链表是空的，一个节点都没有。此时插入一个新的节点，该节点成为循环链表中的唯一节点，那么next指针指向节点自己，如图4.17（a）所示。第2种可能是开始的时候链表中只有一个节点，插入一个新的节点之后，两个节点的next指针互相指向对方，如图4.17（b）所示。

解

public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode5;listNode5.next = listNode6;listNode6.next = listNode1;ListNode result = insert(listNode1, 4);while (result != null) {System.out.println(result.val);result = result.next;}}public static ListNode insert(ListNode head, int insertVal) {ListNode node = new ListNode(insertVal);if (head == null) {// 没有节点head = node;head.next = head;}else if (head.next == head) {// 只有一个节点head.next = node;node.next = head;}else {insertCore(head, node);}return head;}private static void insertCore(ListNode head, ListNode node) {ListNode cur = head;ListNode next = head.next;ListNode biggest = head;while (!(cur.val <= node.val && next.val >= node.val) && next != head) {cur = next;next = next.next;if (cur.val >= biggest.val)biggest = cur;}if (cur.val <= node.val && next.val >= node.val) {cur.next = node;node.next = next;}else {node.next = biggest.next;biggest.next = node;}}
}