amazon oa2 - insert a value into a cycled linked list

时间:2023-03-10 04:29:22
amazon oa2 - insert a value into a cycled linked list

遍历,一共有三种情况,

1. pre <= x <= current

2. 遍历到了head时,x>tail 或者 x<=head (不会等于tail)

3. 遍历回aNode或同值的Node,此时直接插到此Node的前面

public void insert(Node aNode, int x) {
  ListNode last = aNode;
  ListNode current = aNode.next;
  while (current.val != aNode.val) {
    if(last.val<=x && x<=current.val) {
      insertbtw(last,current,x);
      return;
    }
    else {
      if (last.val>current.val && (last.val<x || x<=current.val)) {
        insertbtw(last,current,x);
        return;
      }
    }
    last = current;
    current = current.next;
  }
  if(!inserted) {
    insertbtw(last,current,x);
  }
  return;
}

public void insertbtw(ListNode last, ListNode current, int x) {
  ListNode temp = new ListNode(x);
  last.next = temp;
  temp.next = current;

  return;

}