向有序的环形单链表中插入新节点

【说明】：

本文是左程云老师所著的《程序员面试代码指南》第二章中“向有序的环形单链表中插入新节点”这一题目的C++复现。

本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

感谢左程云老师的支持。

【题目】：

一个环形单链表从头节点 head 开始不降序，同时由最后的节点指向头节点。给定这样的一个环形单链表的头节点 head 和一个整数 num，请生成节点值为 num 的新节点，并插入到这个环形链表中，保证调整后的链表依然有序。

【思路】：

解法：注意头节点的处理

【编译环境】：

CentOS6.7（x86_64）

gcc 4.4.7

【实现】：

实现及测试代码：

1 /*
 2  *文件名：list_insert.cpp
 3  *作者
 4  *摘要：向有序的环形链表中插入新节点
 5  */
 6 
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 class Node
12 {
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 }

View Code

注：

转载请注明出处；

转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5448653.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍