/**
 * class ListNode {
 *   public int value;
 *   public ListNode next;
 *   public ListNode(int value) {
 *     this.value = value;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  public ListNode insert(ListNode head, int value) {
    // write your solution here
    //第一遍写的代码， 很多冗余，没考虑清楚，实际上是要找到最后一个小于等于val的点。
    // if (head == null) {
    //   return new ListNode(value);
    // }
    // ListNode newNode = new ListNode(value);
    // ListNode dummy = new ListNode(0);
    // dummy.next = head;
    // head = dummy;
    // while (head != null && head.next != null) {
    //   if (head.next.value >= value) {
    //     ListNode next = head.next;
    //     head.next = newNode;
    //     newNode.next = next;
    //     return dummy.next;
    //   }
    //   head = head.next;
    // }
    // head.next = newNode;
    // return dummy.next;

    //第二遍的代码清洁很多。
    ListNode newNode = new ListNode(value);
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    head = dummy;
    while (head.next != null && head.next.value <= value) {
      head = head.next;
    }
    newNode.next = head.next;
    head.next = newNode;
    return dummy.next;
  }
}