5_2环形链表插值

这题的后台判题是错误的，需要将环形列表的最后节点的next指向NULL

有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序。

给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值。

测试样例：
输入：[1,3,4,5,7],[1,2,3,4,0],2
返回：{1,2,3,4,5,7}

/*
   struct ListNode {
   int val;
   struct ListNode *next;
   ListNode(int x) : val(x), next(NULL) {}
   };*/
class InsertValue {
    public:
        // 构造环形链表
        ListNode* make_list(const vector<int> A, const vector<int> nxt)
        {
            struct ListNode *p_start = new ListNode(A[0]);
            struct ListNode *end = p_start;
            struct ListNode *head = p_start;
            int idx = nxt[0];
            while(idx != 0){
                struct ListNode *p_node = new ListNode(A[idx]);
                end->next = p_node;
                end = p_node;
                idx = nxt[idx];
                if(head->val > p_node->val){
                    head = p_node;
                }
            }
            end->next = NULL;  //end->next = NULL; //应该是后面这样
            return head;
        }



        ListNode* insert(vector<int> A, vector<int> nxt, int val) {
            // write code here

            if(A.size()<1){
                return NULL;
            }
            struct ListNode *new_node = new ListNode(val);
            ListNode *head = make_list(A, nxt);
            ListNode *p_curr = head, *p_pre = NULL;

            do{
                if(val < p_curr->val){
                    if(p_pre != NULL){
                        p_pre->next = new_node;
                        new_node->next = p_curr;
                        return head;
                    }else{
                        new_node->next = p_curr;
                        head = new_node;
                        return head;
                    }
                }
                p_pre = p_curr;
                p_curr = p_curr->next;
            }while(p_curr != NULL);
            p_pre->next = new_node;
            new_node->next = NULL;  //new_node->next = head; // 应该是后面这样
            return head;
        }
};