1 #include<iostream>
 2 #include<list>
 3 
 4 using namespace std;
 5 // list 构造函数
 6 void test01()
 7 {
 8     list<int> lst1;
 9     lst1.push_back(10);
10     lst1.push_back(20);
11     lst1.push_back(30);
12     list<int> lst2(lst1);//拷贝构造函数
13     list<int> lst3(5, 10);//构造函数
14     list<int> lst4;
15     lst4.assign(lst3.begin(), lst3.end());
16 }
17 
18 // list 数据元素的插入与删除操作
19 void test02()
20 {
21     list<int> lst1;
22     lst1.push_back(30);
23     lst1.push_front(20);//20 30
24     lst1.insert(lst1.begin(), 10);//10 20 30  // 相当于 push_front
25     lst1.insert(lst1.end(), 40);//10 20 30 40 // 相当于 push_back
26     list<int>::iterator itr = lst1.begin();
27     itr++;
28     itr++;
29     lst1.insert(itr, 999);//10 20 999 30 40
30     lst1.push_back(999); //10 20 999 30 40 999
31     auto itr_ = lst1.begin();
32     itr_++;
33     lst1.erase(lst1.begin(), itr_);// [ , )左闭右开  20 999 30 40 999
34     lst1.remove(999);//删除容器中所有值为999的元素    20 30 40 
35 }
36 int main()
37 {
38     test01();
39     test02();
40     return 1;
41 }

  1 #include<iostream>
  2 #include<set>
  3 using namespace std;
  4 
  5 class Node
  6 {
  7 public:
  8     int data_;//数据阈
  9     Node* next_;//指针阈
 10 public:
 11     Node():data_(-1), next_(nullptr) {}
 12 };
 13 
 14 class List
 15 {
 16 public:
 17     List()
 18     {
 19         this->head_ = new Node();// 不分配空间，下面赋值是不合理的！
 20                                  //this->head_->data_ = 0;//多余？
 21         this->head_->next_ = nullptr;
 22         this->size_ = 0;
 23     };
 24     void insert(int pos, int value);
 25     void remove(int pos);
 26     int get_reverse_element(int reverse_pos);//链表中倒数第k个节点
 27     void reverse();
 28 
 29     int operator[](int i);
 30     void print();
 31     ~List();
 32 
 33 
 34 public:
 35     Node* head_;
 36     int size_;//维护一个size
 37 };
 38 //在第pos个元素前一个位置插入（创建、找到位置、入链表）
 39 void List::insert(int pos, int value)
 40 {
 41     if (pos < 0 || pos > size_)
 42         return;
 43 
 44     //创建新的节点接受数据
 45     Node* newnode = new Node();
 46     newnode->data_ = value;
 47     //cout << "newnode->data_ = " << *newnode->data_ << endl;
 48     newnode->next_ = nullptr;
 49 
 50     //利用辅助指针找到pos前一个节点
 51     // 其实这里不断next，无非就是希望p_curr = nullptr
 52     // 然后56行 让newnode->next_  = nullptr（这个nullptr是从head_->next 传过来的）；也就是尾部插入嘛
 53     // 而循环链表 同理 让newnode->next_  = &(head_)（这个 &(head_) 是从head_->next 传过来的）；
 54     Node* p_curr = head_;
 55     for (int i = 0; i < pos; i++) //这个for循环本质上是head_->next_->next_......
 56     {
 57         p_curr = p_curr->next_;
 58     }
 59     //现在p_curr就是pos前一个节点的指针阈
 60     //新节点入链表
 61     newnode->next_ = p_curr->next_;//右边
 62     p_curr->next_ = newnode;//左边
 63     size_++;
 64 }
 65 
 66 void List::remove(int pos)
 67 {
 68     if (pos < 0 || pos > size_)
 69     {
 70         return;
 71     }
 72     Node* p_curr = head_;
 73     for (int i = 0; i < pos; i++)// 3
 74     {
 75         p_curr = p_curr->next_;
 76     }
 77     p_curr->next_ = p_curr->next_->next_;
 78     size_--;
 79 }
 80 
 81 //链表中倒数第k个节点
 82 int List::get_reverse_element(int reverse_pos)
 83 {
 84     int pos = size_ - reverse_pos;
 85     Node* p_curr = head_;
 86     for (int i = 0; i < pos; i++)
 87     {
 88         p_curr = p_curr->next_;
 89     }
 90     return p_curr->data_;
 91 }
 92 
 93 //反转链表
 94 void List::reverse()
 95 {
 96     // head   -> 1 -> 2 -> 3 -> 4 -> nullptr
 97     //nullptr <- 1 <- 2 <- 3 <- 4
 98 
 99     Node* p_curr = head_->next_;
100     Node* p_prev = nullptr;
101     while (p_curr != nullptr)
102     {
103         Node* p_next = p_curr->next_;
104         if(p_curr->next_ == nullptr)
105         {
106             head_->next_ = p_curr;
107         }
108         p_curr->next_ = p_prev;
109         p_prev = p_curr;
110         p_curr = p_next;
111     }
112 }
113 
114 int List::operator[](int i)
115 {
116     Node* p_curr = head_;
117     int count = 0;
118     while (count <= i)
119     {
120         p_curr = p_curr->next_;
121         count++;
122     }
123     return p_curr->data_;
124 }
125 void List::print()
126 {
127     if (size_ == 0)
128     {
129         cout << "size = 0" << endl;
130         return;
131     }
132     //遍历
133     Node* p_curr = head_->next_;//【注意这里next】
134     while (p_curr != nullptr)
135     {
136         cout << p_curr->data_ << " ";
137         p_curr = p_curr->next_;
138     }
139     cout << endl;
140 }
141 List::~List()
142 {
143     while (size_ != 0)
144     {
145         Node* p_curr = head_;
146         for (int i = 0; i < (size_ - 1); i++)// 012345 i < 5
147         {
148             p_curr = p_curr->next_;//for循环执行完，p_curr指向4
149         }
150         delete p_curr->next_;//删除最后一个元素
151         p_curr->next_ = nullptr;//末尾元素 空指针
152         size_--;
153         print();
154     }
155     delete head_; //【这个容易忘记！】
156     cout << "delete!" << endl;
157 }
158 
159 //合并两个排序链表
160 void mergeLists(List& list3, List& list4, List& list34)
161 {
162     Node* p_curr3 = list3.head_->next_;
163     Node* p_curr4 = list4.head_->next_;
164     Node* p_curr34 = list34.head_->next_;
165     int location = 0;
166     while ((p_curr3 != nullptr) || (p_curr4 != nullptr))
167     {
168         if ((p_curr3 != nullptr) && (p_curr4 != nullptr))
169         {
170             if (p_curr3->data_ < p_curr4->data_)
171             {
172                 list34.insert(location, p_curr3->data_);
173                 location++;
174                 list34.insert(location, p_curr4->data_);
175                 location++;
176             }
177             else
178             {
179                 list34.insert(location, p_curr4->data_);
180                 location++;
181                 list34.insert(location, p_curr3->data_);
182                 location++;
183             }
184             p_curr3 = p_curr3->next_;
185             p_curr4 = p_curr4->next_;
186         }
187         else if ((p_curr3 != nullptr) && (p_curr4 == nullptr))
188         {
189             list34.insert(location, p_curr3->data_);
190             location++;
191             p_curr3 = p_curr3->next_;
192         }
193         else if ((p_curr3 == nullptr) && (p_curr4 != nullptr))
194         {
195             list34.insert(location, p_curr4->data_);
196             location++;
197             p_curr4 = p_curr4->next_;
198         }
199     }
200 }
201 
202 
203 int main()
204 {
205     List list1;
206     //插入
207     for (int i = 0; i < 15; i++)
208     {
209         list1.insert(i, i);
210     }
211 
212     //删除
213     list1.remove(10);
214     list1.remove(5);
215     //打印
216     list1.print();
217     list1.reverse();
218     list1.print();
219     //访问倒数元素
220     for (int i = 1; i < 4; i++)
221     {
222         cout << "倒数第" << i << "个元素是：" << list1.get_reverse_element(i) << endl;
223     }
224     list1.insert(2, 9999);
225     //重载符[]
226     for (int i = list1.size_ - 1; i >= 0; i--)
227     {
228         cout << list1[i] << " ";
229     }
230     cout << endl;
231     List list2;
232     list2.insert(0, 10);
233     list2.insert(1, 20);
234     list2.insert(2, 30);
235     list2.print();
236     int size2 = list2.size_;
237 
238     //合并两个排序链表
239     List list3, list4;
240     for (int i = 0; i < 5; i++)
241     {
242         list3.insert(i, 2 * i);
243         list4.insert(i, 2 * i + 1);
244     }
245     list4.insert(5, 12);
246     list4.insert(6, 21);
247     list3.print();
248     list4.print();
249 
250     List list34;
251     mergeLists(list3, list4, list34);
252     list34.print();
253 
254 
255     return 1;
256 }