假设我们有一个来自循环链表的节点,该节点以递增顺序排序,我们必须定义一个函数,以将值insertVal插入列表中,从而使其保持为已排序的循环表。
该节点可以是对列表中任何单个节点的引用,并且不一定是循环列表的第一个值。如果有多个合适的插入位置,我们可以选择任何位置插入新值。如果列表为空,那么我们必须创建一个新的单个循环列表,并将引用返回到该单个节点。否则,我们应该返回原始的给定节点。
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Node { public: int val; Node* next; Node() {} Node(int _val) { val = _val; next = NULL; } Node(int _val, Node* _next) { val = _val; next = _next; } }; class Solution { public: Node* insert(Node* head, int val) { if(!head){ head = new Node(val); head->next = head; } else{ Node* curr = head->next; Node* prev = head; Node* temp = new Node(val); bool done = false; while(1){ if (curr->val >= val && prev->val <= val) { prev->next = temp; temp->next = curr; done = true; break; } if (prev->val > curr->val) { if (prev->val <= val || val <= curr->val) { prev->next = temp; temp->next = curr; done = true; break; } } if (curr == head) break; prev = curr; curr = curr->next; } if(!done){ temp->next = head; prev->next = temp; head = temp; } } return head; } }; main(){ Solution ob; Node *head = new Node(3); head->next = new Node(4); head->next->next = new Node(1, head); ob.insert(head, 2); Node *temp = head; if (head != NULL){ do{ cout << temp->val << " "; temp = temp->next; } while (temp != head); } }
node *head = new Node(3); head->next = new Node(4); head->next->next = new Node(1, head); insertVal = 2
输出结果
3 4 1 2