描述
给一个来自已经排过序的循环链表的节点，写一个函数来将一个值插入到循环链表中，并且保持还是有序循环链表。给出的节点可以是链表中的任意一个单节点。返回插入后的新链表。
注意事项
3->5->1 是一个循环链表，所以 3 是 1 的下一个节点。3->5->1 与 5->1->3 相同
样例
给一个链表：3->5->1
插入值 4
返回 5->1->3->4
思路
循环链表的插入要考虑四种情况：
- 链表为空
- 链表只有一个结点
- 链表值不全部相等时的两种插入：
a. 顺序排列的合适位置
b. 最大值最小值的中间插入- 链表值全部相等时，在表头或表尾的任意插入
代码
- version1
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param node a list node in the list
* @param x an integer
* @return the inserted new list node
*/
public ListNode insert(ListNode node, int x) {
// 链表为空时,新建一个结点,node.value = x,结点的next指针指向自己
if (node == null) {
node = new ListNode(x);
node.next = node;
return node;
}
// 在链表内部寻找合适的插入位置
// current是当前结点，node是链表头结点
ListNode current = node;
ListNode prev = null;
do {
/* prev和current都向后移一位
* 不能写成prev.next = current;
* 如果是普通链表可能问题不大，但循环链表的话会出问题，
* 因为循环链表实际上就是一个环形链表，
* 没有头尾，这种情况下给某一个结点在外面加了一个新的连接结点，
* 在遍历循环链表时一定会出现超时
*/
prev = current;
current = current.next;
// 两种满足条件的插入情况，用break结束循环
if (x <= current.val && x >= prev.val) {
break;
}
if ((prev.val > current.val) && (x < current.val || x > prev.val)) {
break;
}
// 刚开始current = node,不断后移,若current再次等于node则证明遍历整个链表一圈
} while (current != node);
// 链表内部位置都不满足条件，可以说明链表都是值一样的结点，直接在边缘插入
// 创建新结点，把新结点插入到合适的位置
ListNode newNode = new ListNode(x);
newNode.next = current;
prev.next = newNode;
return newNode;
}
}
- version2 不用do while 逻辑更清晰些
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/*
* @param node: a list node in the list
* @param x: An integer
* @return: the inserted new list node
*/
public ListNode insert(ListNode node, int x) {
// 链表为空
if (node == null) {
node = new ListNode(x);
node.next = node;
return node;
}
ListNode current = node;
ListNode prev = null;
// 链表只有一个结点
prev = current;
current = current.next;
if (current == node) {
ListNode newNode = new ListNode(x);
current.next = newNode;
newNode.next = current;
}
// 链表结点值不全部相等
// 当链表值相等时，下面的 if 根本不会执行
while (current != node) {
if ((prev.val <= x && x <= current.val) ||
(prev.val > current.val && (prev.val < x || x < current.val))) {
ListNode newNode = new ListNode(x);
prev.next = newNode;
newNode.next = current;
break;
}
prev = current;
current = current.next;
}
// 链表结点值全部相等
ListNode newNode = new ListNode(x);
prev.next = newNode;
newNode.next = current;
return node;
}
}
