Insert into a Sorted Circular Linked List
给一个循环并且排序的linked list, 现在像往里面加一个node, 求加在哪里. 这个题要用双指针, 这样才能找到出现的前后node. 然后有三种情况, 第一种是正常的在最大和最小值中间的node, 这样的node直接接上去就可以了, 第二种是自己就是最大或者最小值. 第三种是环中所有值都一样, 这样很难判断环, 所以要单写出来当corner case.
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _next) {
val = _val;
next = _next;
}
};
*/
class Solution {
public Node insert(Node head, int insertVal) {
if(head == null) {
Node n = new Node(insertVal);
n.next = n;
return n;
}
Node prev = head;
Node cur = head.next;
boolean done = false;
do {
if(prev.val <= insertVal && insertVal <= cur.val) {
done = true;
} else if(prev.val > cur.val){ // at the end
if(insertVal <= cur.val || insertVal >= prev.val) {
done = true;
}
}
if(done) {
prev.next = new Node(insertVal);
prev.next.next = cur;
return head;
} // if not done
else {
prev = cur;
cur = cur.next;
}
} while(prev != head);
// uniform value;
prev.next = new Node(insertVal);
prev.next.next = cur;
return head;
}
}