题解 | #无环单链表插值#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode insert (int[] A, int val) {
        // write code here
        // 记录pre，node，并使用虚拟节点，保证一致性
        if (A == null || A.length == 0) {
            return null;
        }
        // 构造虚拟头节点
        ListNode head = new ListNode(-1);
        boolean flag = false;
        // 开始构造链表
        ListNode node = head, pre = head;
        ListNode newNode = head;
        for (int i = 0; i < A.length; ++i) {
            node = new ListNode(A[i]);
            if (!flag && A[i] > val) {
                newNode = new ListNode(val);
                pre.next = newNode;
                newNode.next = node;
                pre = node;
                flag = true;
            } else {
                pre.next = node;
                pre = pre.next;
            }
        }
        // 如果val没有添加到链表中
        if (!flag) {
            node.next = new ListNode(val);
        }
        return head.next;
    }
}