记录下链表操作，留着回忆的时候看
建立一个新头节点，然后把原来链表的第一个元素不断插入新头节点后
这个是只有头指针，没有头节点（注意这个区别，我因为没注意区别，苦思了好久，才发现）
Linklist *reverseList(Linklist *head) { Linklist *newhead = NULL; Linklist *node; while(head != NULL){ //对之前的链表删除第一个元素 node = head; head = head->next; //把从旧链表拆下的元素插入到新链表头节点后 node->next = newhead; newhead = node; } return newhead; }至于有头节点的，其实你可以把头节点的指向第一个元素的指针当作上面头指针的情况就可以了。 这里是我魔改的带有头节点的链表反转的代码
Linklist *reverseList(Linklist *head) { Linklist *newhead = NULL; Linklist *node; Linklist *q = head->next; while(q != NULL){ //对之前的链表删除第一个元素 node = q;//把头节点指向的第一个元素的指针当作头指针 //再参考上面无头节点的链表反转操作， q = q->next; //把从旧链表拆下的元素插入到新链表头节点后 node->next = newhead; newhead = node; } Linklist *temp = newhead; newhead = head; //这里还是利用了原来的头节点，之前想new一个，但是发现会有内存泄漏的可能，算了算了 newhead->next= temp; return newhead; }这里其实还有一种方法，先留个坑，明天学完rmq的dp再填
尾节点的next指针不再指向NULL，而是指向头节点 循环链表的基本操作（凑字数，其实跟单链表差不多）
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <string> #include <cmath> #include <cstdlib> using namespace std; const int MAXN = 1000005; const int Size = 26; struct Linklist { int data; Linklist *next; }; //创建并初始化链表 Linklist *creat(int n) { Linklist *head_node,*temp_node,*end_node; head_node = new Linklist; head_node->next = head_node; if(head_node == NULL){ cout<<"分配内存失败"<<endl; return NULL; } end_node = head_node; for(int i = 0; i < n; i++){ temp_node = new Linklist; cin>>temp_node->data; end_node->next = temp_node; end_node = temp_node; } end_node->next= head_node; return head_node; } //n为第n个节点 bool find(Linklist *head,int n,int &data) { Linklist *node = head->next; for(int i = 2; i <= n&&node != head; i++){ node = node->next; } if(node == head){ cout<<"节点不存在"<<endl; return false; } data = node->data; return true; } //修改函数,val为修改后该被修改节点的值 bool change(Linklist *head,int n,int val) { Linklist *node = head->next; for(int i = 2; i <= n&&node != head; i++){ node = node->next; } if(node == head){ cout<<"不存在该节点"<<endl; return false; } node->data = val; return true; } //删除节点 bool del(Linklist *head,int n) { Linklist *temp = head,*fnode; for(int i = 0; i < n&&temp != NULL; i++){ fnode = temp; temp = temp->next; } if(temp == NULL){ cout<<"节点不存在"<<endl; return false; } fnode->next = temp->next; delete temp; return true; } //插入节点,再n后插入 bool insert(Linklist *head,int n) { Linklist *temp = head->next , *newnode; for(int i = 2; i <= n&&temp != head; i++){ temp = temp->next; } if(temp == head){ cout<<"该节点不存在"<<endl; return false; } newnode = new Linklist; cin>>newnode->data; newnode->next = temp->next; temp->next = newnode; return true; } //输出链表 void display(Linklist *head) { Linklist *now = head->next; while(now != head){ cout<<now->data<<endl; now = now->next; } } // //释放内存 // void delete_all_Linklist(Linklist * head) // { // if(head->next != NULL){ // delete_all_Linklist(head->next); // } // delete head; // head = NULL; // } void delete_all_Linklist(Linklist *&head) { Linklist *p = head->next; while(p != head){ Linklist *q = p->next; delete p; p = q; } delete head; head = NULL; } int main() { int n;//初始化的元素数量 cin>>n; Linklist *head = creat(n); display(head); cout<<endl; insert(head,2);//再第二个位置后插入 display(head); cout<<endl; del(head,3);//删除上一步插入的节点； display(head); cout<<endl; change(head,2,1); display(head); delete_all_Linklist(head);//释放内存 return 0; }具体图示看这里
//实现代码 #include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <string> #include <cmath> #include <cstdlib> using namespace std; const int MAXN = 1000005; const int Size = 26; struct double_Linklist { int data; double_Linklist *prev; double_Linklist *next; }; typedef double_Linklist deLinklist; //双向链表的建立 deLinklist *creat(int n , deLinklist *&tail) { deLinklist *head , *plast, *pnext; head = new deLinklist; if(head == NULL){ cout<<"分配内存失败"<<endl; return NULL; } head->next = head->prev = NULL; plast = head; for(int i = 0; i < n; i++){ pnext = new deLinklist; cin>>pnext->data; plast->next = pnext; pnext->prev = plast; plast = plast->next ; } plast->next= NULL; tail = plast;//获取尾节点地址 return head; } //n为第n个节点 bool find(deLinklist *head,int n,int &data) { deLinklist *node = head; for(int i = 0; i < n&&node != NULL; i++){ node = node->next; } if(node == NULL){ cout<<"节点不存在"<<endl; return false; } data = node->data; return true; } //修改函数,val为修改后该被修改节点的值 bool change(deLinklist *head,int n,int val) { deLinklist *node = head; for(int i = 0; i < n&&node != NULL; i++){ node = node->next; } if(node == NULL){ cout<<"不存在该节点"<<endl; return false; } node->data = val; return true; } //删除节点 bool del(deLinklist *head,int n) { deLinklist *temp = head,*fnode; for(int i = 0; i < n&&temp != NULL; i++){ //fnode = temp; temp = temp->next; } if(temp == NULL){ cout<<"节点不存在"<<endl; return false; } //fnode->next = temp->next; //将要删除节点的前一个节点next指针指向要删除节点的下一个指针 temp->prev->next = temp->next; //如果不是删除尾节点，那么要删除节点的下一个节点的prev指向要删除节点的上一个节点 if(temp->next != NULL) temp->next->prev = temp->prev; delete temp; return true; } //插入节点,再n后插入 bool insert(deLinklist *head,int n) { deLinklist *temp = head, *newnode; for(int i = 0; i < n&&temp != NULL; i++){ temp = temp->next; } if(temp == NULL){ cout<<"该节点不存在"<<endl; return false; } newnode = new deLinklist; cin>>newnode->data; newnode->prev = temp;//待插入节点的prev指针指向前一个节点 //待插入节点的next指向要插入位置节点next指针指向的节点 newnode->next = temp->next; //当前位置节点next指针指向的节点的prev指向待插入节点 if(temp->next != NULL) temp->next->prev = newnode;//要注意判断是不是在尾部插入 temp->next = newnode;//要插入位置节点的next指针指向待插入节点 return true; } //输出链表 void display(deLinklist *head) { deLinklist *now = head->next; while(now != NULL){ cout<<now->data<<endl; now = now->next; } cout<<"NULL"<<endl; } void delete_all_Linklist(deLinklist * &head , deLinklist * &tail) { while(NULL != head){ deLinklist *p = head->next; delete head; head = p; } tail = NULL; } int main() { int n;//初始化的元素数量 cin>>n; deLinklist *tail; deLinklist *head = creat(n , tail); display(head); insert(head,2);//再第二个位置后插入 display(head); del(head,3);//删除上一步插入的节点； display(head); delete_all_Linklist(head , tail);//释放内存 return 0; }