有一个整数val，如何在节点值有序的环形链表中插入一个节点值为val的节点，并且保证这个环形单链表依然有序。 给定链表的信息，及元素的值A及对应的nxt指向的元素编号同时给定val，请构造出这个环形链表，并插入该值。 测试样例： [1,3,4,5,7],[1,2,3,4,0],2 返回：{1,2,3,4,5,7}
这道题bug太多，首先构造的时候并不是环形列表而是单链表，链表的头部并未指向值最小的节点（是在题目样例中默认的）。在做题的过程中对于链表问题可以构造多一个节点，让这个节点指向头结点，这样可以规避很多边界可能出现的问题。正常对于环形列表，头指针必须指向链表中的最小值。如果插入的值比链表中所有的值都大，那么插入链表尾并返回头，如果比所有值都小则插入链表头返回插入的指针（加节点指向头可以规避这个问题）。
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {}};*/class InsertValue {public: ListNode* insert(vector<int> A, vector<int> nxt, int val) { if(A.empty()) return new ListNode(val); ListNode* PRehead=new ListNode(0); ListNode* res=prehead; int min=A[0]; int length=nxt.size(); int i=0; while(length--) { prehead->next=new ListNode(A[i]); prehead=prehead->next; i=nxt[i]; } ListNode *before=res; ListNode *after=res->next; while(after) { if(val<after->val) { ListNode* nodetemp=new ListNode(val); before->next=nodetemp; nodetemp->next=after; return res->next; } else { before=after; after=after->next; } } ListNode* nodetemp=new ListNode(val); before->next=nodetemp; return res->next; }};新闻热点
疑难解答
