【说明】：
本文是左程云老师所著的《程序员面试代码指南》第二章中“向有序的环形单链表中插入新节点”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】：
一个环形单链表从头节点 head 开始不降序，同时由最后的节点指向头节点。给定这样的一个环形单链表的头节点 head 和一个整数 num，请生成节点值为 num 的新节点，并插入到这个环形链表中，保证调整后的链表依然有序。
【思路】：
解法：注意头节点的处理
【编译环境】：
CentOS6.7（x86_64）
gcc 4.4.7
【实现】：
实现及测试代码：
1 /* 2 *文件名：list_insert.cpp 3 *作者 4 *摘要：向有序的环形链表中插入新节点 5 */ 6 7 #include8 9 using namespace std;10 11 class Node12 {13 public:14 Node(int data)15 {16 value = data;17 next = NULL; 18 }19 public:20 int value;21 Node *next;22 };23 24 Node* insertNum(Node *head,int num)25 {26 Node *n = new Node(num);27 if(NULL == head)28 {29 n->next = n;30 return n;31 }32 33 Node *pre = head;34 Node *cur = head->next;35 while(cur != head)36 {37 if(pre->value <= num && cur->value >= num)38 break;39 pre = cur;40 cur = cur->next;41 }42 pre->next = n;43 n->next = cur;44 return head->value < num ? head : n;45 }46 47 //打印环形链表48 void printList(Node *head)49 {50 Node *pre = head;51 Node *cur = head->next;52 while(cur != head)53 {54 cout << pre->value << " ";55 pre = cur;56 cur = cur->next;57 }58 cout << pre->value << endl;59 }60 61 int main()62 {63 Node *head = NULL;64 Node *ptr = NULL;65 66 for(int i =1;i<4;i++)//构造链表67 {68 if(NULL == head)69 { 70 head = new Node(i);71 ptr = head;72 continue;73 }74 ptr->next = new Node(i);75 ptr = ptr->next; 76 }77 ptr->next = head; //环形链表78 79 cout << "Before insertion:" << endl;80 printList(head);81 cout << "After insertion:" << endl;82 head = insertNum(head,0);83 printList(head);84 return 0;85 }
注：
转载请注明出处；
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。