链表概念的引入
struct ListNode { int num; ListNode* next; };
创建无序链表，依次输入各节点数据，以-1结束。循环读入数据，若数据不为-1，就申请一个新节点，将数据赋给新节点，在链表尾部加上该节点。加节点的时候，要分情况，（1）首节点（2）中间节点*（3）尾节点
ListNode* Creat() { ListNode *p1,*p2,*head; int a; head =NULL; cin>>a; while(a!=-1) { p1=new ListNode; p1->num = a; if(head==NULL) { head =p2=p1; } else { p2->next=p1; p2=p1; } cin>>a; } if(head!=NULL) p2->next=NULL; return head; }
输出链表，函数通过头结点传参，这里要注意尽量使用const修饰，避免函数修改节点数据
void print(const ListNode* head) { const ListNode *p; p=head; while(p!=NULL) { cout << setw(4)<<p->num; p=p->next; } cout<<endl; }
查找特定节点，在链表中查找数据值为x的节点，并返回该节点的指针，这里也使用const修饰参数
const ListNode* Search(const ListNode* head,int x) { const ListNode* p; p=head; while(p!=NULL) { if(p->num == x) return p; p=p->next; } return NULL; }
删除一个节点，比如值等于x的节点，下面的程序只删除第一个值为x的节点，在删除过程中，也要分情况，（1）如果是空链表，就直接返回NULL（2）如果删除的节点刚好是头结点，那么将下一个节点设为头结点（3）如果是其他节点，就正常删除。删除过程也是从头结点遍历，这里用两个指针，一个用来遍历，一个用来保存前一个节点，这样删除的时候，可以用前一个节点的next指向该节点后面的节点。
ListNode* Delete_one_node(ListNode* head,int x) { ListNode *p1,*p2; if(head == NULL) { cout<<"the list is null"<<endl; return NULL; } p1=head; while(p1->num!=x && p1->next!= NULL) { p2=p1; p1=p1->next; } if(p1->num == x) { if(p1==head) head=p1->next; else p2->next=p1->next; delete p1; cout<<"delete finished"<<endl; } else cout<<"sorry,dont find the node x"<<endl; return head; }
释放链表，也是传参链表的头结点，这里同样借助一个指针来逐个释放节点，从头结点开始，把头结点赋给新节点，每次将头结点往后移一位，删除节点，相当于删除了原来的头结点
void Delete_all(ListNode* head) { ListNode *p; while(head) { p=head; head = head->next; delete p; } }
插入一个节点，这个函数的前提是，在函数执行前，已建立了一个节点值为升序的链表，插入一个新节点之后，链表依然保证升序。插入时，也要考虑多种情况，（1）链表是空链表，直接将新节点作为头结点（2）插入在头结点之前，这里依然用两个节点，一个p1从头结点开始判断遍历，一个p2永远指向p1之前，插入在头结点之前，直接将新节点作为头结点（3）插入在链表中间（也是p1节点之前），直接将p2的next指向新节点（4）插入在尾节点之后，要注意要把新节点的next赋成NULL
ListNode* Insert(ListNode* head,ListNode *p) { ListNode *p1,*p2; if(head==NULL) { head=p; p->next=NULL; return head; } p1=head; while(p->num>p1->num && p1->next !=NULL) { p2=p1; p1=p1->next; } if(p->num <= p1->num) { p->next=p1; if(head==p1) head=p; else p2->next = p; } else { p1->next=p; p->next=NULL; } return head; }
原文：https://www.cnblogs.com/mini-coconut/p/8971967.html