Insert into a Sorted Circular Linked List
给一个循环并且排序的linked list, 现在像往里面加一个node, 求加在哪里. 这个题要用双指针, 这样才能找到出现的前后node. 然后有三种情况, 第一种是正常的在最大和最小值中间的node, 这样的node直接接上去就可以了, 第二种是自己就是最大或者最小值. 第三种是环中所有值都一样, 这样很难判断环, 所以要单写出来当corner case.
|
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 54 55 |
/* // 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; } } |