链表

一、理论基础

1.链表是一种由指针串联起来的线性结构，包括数据域和指针域，可分为单链表、双链表和循环链表

2.循环链表可以用来解决约瑟夫环问题，链表的头为head

3.存储方式：它是由指针域链接起来的，在内存中不是连续分布的

4.链表的定义：

 //单链表
 struct listnode{
     int val;//节点上存储的元素
     listnode *next; //指向下一个节点的指针
     //listnode(int x): val(x), next(NULL){} //节点的构造函数
 }
 //创建链表
 listnode* createlist() 
 {
     linstnode* headnode = new listnode(0);
     headnode ->next = NULL;
     return headnode;
 }
 //创建结点
 listnode* createnode(int val)
 {
     listnode* newnode=new listnode(0);
     newnode->val=val;
     newnode->next=NULL;
 }
 //打印链表
 viod printlist(listnode* headnode)
 {
     listnode* pmove=headnode->next;
     while(pmove)
     {
         cout<val<         pmove = pmove->next;
     }   
 }
 //头插入法
 void inputlist(listnode*headnode, int val)
 {
     listnode* newlist = createnode(val); //创建新节点
     newlist ->next = headnode->next;
     headnode ->next = newlist;
 }
 //指定位置删除
 void deletelist(listnode*headnode, int posdata)
 {
     listnode*posnode=headnode->next; //从头结点下一个位置开始寻找
     listnode*posnodefront = headnode; //删除指定结点上一个节点
     if(posnode==NULL)
        cout<<"链表为空无法删除!"<     else{
         while(posnode->val!=posdata)
         {
             posnodefront->next = posnode;
             posnode= posnode->next;
             if(posnode==NULL)
                return
         }
         posnodefront->next=postnode->next;
         delete postnode; //释放存储空间
     }
 ?
 ?
 }
 ?
 //初始化
 Listnode* head= new Listnode(5);

5.删除：预删除节点的上一个节点指针，指向预删除下一个节点，同时释放预删除节点内存。

6.适用情况：数据量不固定，频繁增删，较少查询，条件相反使用数组。

二、移除链表元素

1）移除头结点：将头结点往后移动一位；设立一个虚拟头结点，采用其他位置结点移除方法进行删除

当返回头结点时，不要忘记 return dummynode->next

三、反转链表（倒序排列）

双指针法从头开始翻转，自定义一个空节点，暂存临时标记的下个节点。

TRANSLATE with

Bing Webmaster Portal

• 中文（简体）
• 中文（繁体）
• 丹麦语
• 乌克兰语
• 乌尔都语
• 亚美尼亚语
• 俄语
• 保加利亚语
• 克罗地亚语
• 冰岛语
• 加泰罗尼亚语
• 匈牙利语
• 卡纳达语
• 印地语
• 印尼语
• 古吉拉特语
• 哈萨克语
• 土耳其语
• 威尔士语
• 孟加拉语
• 尼泊尔语
• 布尔语(南非荷兰语)
• 希伯来语
• 希腊语
• 库尔德语
• 德语
• 意大利语
• 拉脱维亚语
• 挪威语
• 捷克语
• 斯洛伐克语
• 斯洛文尼亚语
• 旁遮普语
• 日语
• 普什图语
• 毛利语
• 法语
• 波兰语
• 波斯语
• 泰卢固语
• 泰米尔语
• 泰语
• 海地克里奥尔语
• 爱沙尼亚语
• 瑞典语
• 立陶宛语
• 缅甸语
• 罗马尼亚语
• 老挝语
• 芬兰语
• 英语
• 荷兰语
• 萨摩亚语
• 葡萄牙语
• 西班牙语
• 越南语
• 阿塞拜疆语
• 阿姆哈拉语
• 阿尔巴尼亚语
• 阿拉伯语
• 韩语
• 马尔加什语
• 马拉地语
• 马拉雅拉姆语
• 马来语
• 马耳他语
• 高棉语