无环单链表插值

思路：

1.创建一个新链表的虚的头结点**

2.遍历数组，将每个数组中的值创建一个对应的节点

3.注意分为两种特殊的情况情况讨论：情况一：val的值是插在两个节点中间，val是插在链表的末尾

代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode insert (int[] A, int val) {
        //先创建一个新链表的虚的头结点
        ListNode dummynode=new ListNode(-1);
        ListNode cur=dummynode;
        //由于如果需要插入的节点如果插入到链表的最后，那么就需要特殊处理
        //所以分为两种情况：一种是插在两个节点中间，另一种是插在链表的最后
        boolean flag=true;
        //遍历整个数组，将对应的位置的值创建成新的节点，连在链表上
        //如果发现有大于val的节点，就创建一个节点用来放val,再将对应的节点插在该节点之前
        for(int i=0;i<A.length;i++){
            if(A[i]>val&&flag==true){
                ListNode p=new ListNode(val);
                cur.next=p;
                cur=cur.next;
                flag=false;
            }
            ListNode t=new ListNode(A[i]);
            cur.next=t;
            cur=cur.next;
        }
        //特使情况特殊处理：将val的值插在链表的最后一个节点的后面
        if(flag==true){
            ListNode now=new ListNode(val);
            cur.next=now;
            cur=cur.next;
        }
        return dummynode.next;
    }
}