编写一个程序，在一个已排序的循环链表中插入一个新的节点。例如，假设初始的循环链表如下所示：
插入新的节点7之后，上面的循环链表变为了下面所示：
算法:假设需要插入的新节点为newNode， 则插入操作可以分为下面的3种情形：
1) 链表为空:a) 因为循环链表只有newNode这一个节点，则自我循环.newNode->next = newNode;b) 调整头指针*head = newNode;2) 新节点需要插入到链表头节点的前面:(a) 遍历链表，找出尾节点.while(current->next != *head)current = current->next; (b) 修改尾节点的后向指针.current->next = newNode; (c) 调整newNode的后向指针为原始头节点.newNode->next = *head; (d) 调整头指针，指向新的节点.*head = newNode;3) 新节点需要插入到某个节点的后面:(a) 定位需要被插入节点的位置.while ( current->next!= *head && current->next->data < newNode->data)current = current->next; (b) 将新节点的后向指针调整为定位节点的后向指针newNode->next = current->next; (c) 修改定位节点的后向指针current->next = newNode; 代码实现#include <iostream>//链表节点struct Node{int data;Node *next;};void swap(int *a, int*b){int tmp = *a;*a = *b;*b = tmp;}//在一个已排序的循环链表中插入新节点void sortedInsert(Node** head, Node* newNode){Node* current = *head;// 情形1if (current == NULL){newNode->next = newNode;*head = newNode;}// 情形2else if (current->data >= newNode->data){//如果新节点值小于头节点值，则需要调整尾节点的后向指针while (current->next != *head)current = current->next;current->next = newNode;newNode->next = *head;*head = newNode;}// 情形3else{//定位需要被插入数据的节点while (current->next != *head && current->next->data < newNode->data)current = current->next;newNode->next = current->next;current->next = newNode;}}//在循环链表头部插入新的节点void push(Node **head, int data){Node *newNode = new Node;Node *temp = *head;newNode->data = data;newNode->next = *head;//如果链表不为空，则将最后一个节点的后向指针设置为新节点//即新节点变成了新的头节点。if (*head != NULL){while (temp->next != *head)temp = temp->next;temp->next = newNode;}elsenewNode->next = newNode; //新节点做为链表第一个节点*head = newNode; //调整头节点}//打印循环链表void printList(Node *head){Node *temp = head;if (head != NULL){do{std::cout<<" "<<temp->data<<" ";temp = temp->next;} while (temp != head);}}int main(){const int arrSize = 6;int arr[arrSize] = { 12, 56, 2, 11, 1, 90 };Node *head = NULL;for (int i = 0; i < arrSize; i++){Node *newNode = new Node;newNode->data = arr[i];sortedInsert(&head, newNode);}printList(head);std::cout << std::endl;return 0;}输出:1 2 11 12 56 90时间复杂度: O(n) ，其中n是给定链表中的节点个数代码改进其中，上述代码中的情形2的算法还能优化。可以使用值交换的方法，，避免遍历整个链表。优化后的代码如下所示：// 情形2的代码实现else if (current->data >= newNode->data){swap(&(current->data), &(newNode->data)); //假设存在swap函数newNode->next = (*head)->next;(*head)->next = newNode;}
哪里会顾得上这些。等到时间将矛盾一层层降解为流言是非误解过结
