1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
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 currNode = head, nextNode = head.next;
boolean inserted = false;
do {
if (currNode.val <= nextNode.val) {
if (insertVal == currNode.val || insertVal == nextNode.val
|| (insertVal > currNode.val && insertVal < nextNode.val)) {
currNode.next = newNode;
newNode.next = nextNode;
inserted = true;
break;
}
} else {
if (insertVal >= currNode.val || insertVal <= nextNode.val) {
currNode.next = newNode;
newNode.next = nextNode;
inserted = true;
break;
}
}
currNode = nextNode;
nextNode = nextNode.next;
} while (currNode != head);
if (inserted) {
return head;
}
currNode.next = newNode;
newNode.next = nextNode;
return head;
}
}
|
有点儿小绕. 我们维护两个pointers来走这个circular list. 如果发现能插在curr和next之间的插就完事儿了, 如果遇到curr大于next的情况, 我们说明到达了list的尾部, 此时要单独判断.
list可以分为两种, 一种是首尾相等, 这样的话所有的node都相等, 此时如果我们要插入的值不等于每一个node的值, 我们的逻辑捕捉不到这种情况, 因此最后需要看while循环中是否insert完了. 如果等于每个node的值, 我们的逻辑是可以捕捉到的. 还有一种就是首尾不同的, 此时不管insertVal是大于最大值还是小于最小值亦或是在最小值和最大值之间. 我们的逻辑都能捕捉到.
时间复杂度: O(n) 因为我们要走一圈.
空间复杂度: O(1)
