05 August 2008
循环链表中升序，插入新元素
one pass
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
43
44
45
46
47
48
49
50
51
52
53
// Test case 1: insert(null, 1)
// Test case 2: insert(1->null, 0)
// Test case 3: insert(1->null, 1)
// Test case 4: insert(1->null, 2)
// Test case 5: insert(1->1->1->null, 0)
// Test case 6: insert(1->1->1->null, 1)
// Test case 7: insert(1->1->1->null, 2)
// Test case 8: insert(1->1->3->3->null, 0)
// Test case 9: insert(1->1->3->3->null, 1)
// Test case 10: insert(1->1->3->3->null, 2)
// Test case 11: insert(1->1->3->3->null, 3)
class Solution {
public Node insert(Node start, int x) {
// if start is null, create a node pointing to itself and return
if (start == null) {
Node node = new Node(x, null);
node.next = node;
return node;
}
// is start is NOT null, try to insert it into correct position
Node cur = start;
while (true) {
// case 1A: has a tipping point, still climbing
if (cur.val < cur.next.val) {
if (cur.val <= x && x <= cur.next.val) { // x in between cur and next
insertAfter(cur, x);
break;
}
// case 1B: has a tipping point, about to return back to min node
} else if (cur.val > cur.next.val) {
if (cur.val <= x || x <= cur.next.val) { // cur is the tipping point, x is max or min val
insertAfter(cur, x);
break;
}
// case 2: NO tipping point, all flat
} else {
if (cur.next == start) { // insert x before we traverse all nodes back to start
insertAfter(cur, x);
break;
}
}
// None of the above three cases met, go to next node
cur = cur.next;
}
return start;
}
// insert value x after Node cur
private void insertAfter(Node cur, int x) {
cur.next = new Node(x, cur.next);
}
}
two passes
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
class Solution {
public Node insert(Node start, int x) {
// if start is null, create a node pointing to itself and return
if (start == null) {
Node node = new Node(x, null);
node.next = node;
return node;
}
// if start is not null, try to insert it into correct position
// 1st pass to find max node
Node cur = start;
while (cur.val <= cur.next.val && cur.next != start)
cur = cur.next;
// 2nd pass to insert the node in to correct position
Node max = cur;
Node dummy = new Node(0, max.next); // use a dummy head to make insertion process simpler
max.next = null; // break the cycle
cur = dummy;
while (cur.next != null && cur.next.val < x) {
cur = cur.next;
}
cur.next = new Node(x, cur.next); // insert
Node newMax = max.next == null ? max : max.next; // reconnect to cycle
newMax.next = dummy.next;
return start;
}
}