目录
引言
创建有序单链表
题目
算法思路
代码实现
逆置单链表
题目
算法思路
代码实现
判断单链表是否有环
题目
算法思路
代码实现
取单链表中间节点的数值
题目
算法思路
代码实现
总结
引言
有关单链表的基础操作，如动态分布空间，单链表创建的思路，单链表的增、删、改、毁，笔者已经在博客中详细解析了，有兴趣的小伙伴也可以取看看，
本次介绍的是有关单链表的四道大厂面试典中典，其中的逆置单链表更是重量级，大家放心食用😁
正文
创建有序单链表
题目
创建一个升序或降序的单链表，并打印输出，例如：
输入： 1 5 6 2 3 输出： 1 2 3 5 6
算法思路
算法思路：
s1:每获得一个数据 就创建一个数据结点
s2:把数据写入到数据结点中去
s3:把写好的数据结点加入到链表中去
分情况讨论：
从无到有
从少到多
头插法
尾插法
中间插入
我们将算法思路待人代码中观察
代码实现
Node *create_sort_list() { u4 d; Node *pnew = NULL; //指向 新创建的节点 Node *head = NULL; while(1) { scanf("%d",&d); if(d == 0) //约定输入0，结束输入 break; pnew = malloc(sizeof(*pnew)); //分配空间 pnew->data = d; //将数据写入数据节点 pnew->next = NULL; //将写好的数据节点加入到链表 if(head == NULL) //从无到有 { head = pnew; } else //从少到多 { Node *p = head; Node *pre = NULL; while(p) //找出链表中比新节点大的数据打的节点 { if(p->data > pnew->data) //找到就返回这个节点 { break; } else //没找到就往下遍历，直到p==NULL,即新节点的值是最大的，插到末尾 { pre = p; p = p->next; } } if(p != NULL) { if(p == head) //头插法 { pnew->next = head; //新节点指向链表的第一个，即指向head head = pnew; //然后将head指向新节点 } else //插入中间 { pnew->next = p; pre->next = pnew; } } else //插到末尾 { pre->next = pnew; } } } return head; }
逆置单链表
题目
就地逆置一个链表（不允许申请新的结点空间）
例子：
h: 1 5 3 4
=>
h: 4 3 5 1
要求：
不允许申请新的结点空间
算法思路
把原链表的每一个结点 ，摘下来 ，然后按头插法 加入到新链表。
Node *reverse(Node *h) { //创建一个指向逆置后链表的第一个结点 //创建一个指针p为遍历指针 while(p) { //step 1:把h指向的链表的第一个结点摘下来 //step2: 按照头插法 把p结点 加入到逆置后的链表first //step2.1 从无到有 //step2.2 从少到多 } //返回逆置链表的第一个节点 }
代码实现
Node *reverrse(Node *h) { Node *first = NULL; //创建一个指向逆置后链表的第一个结点 Node *p = h; //创建一个指针p为遍历指针 while(p) { //step 1:把h指向的链表的第一个结点摘下来 h = h->next; p->next = NULL; //step2: 按照头插法 把p结点 加入到逆置后的链表first //step2.1 从无到有 if(first == NULL) { first = p; } else //step2.2 从少到多 { p->next = first; first = p; } p = h; } return first; //返回逆置链表的第一个节点 }
判断单链表是否有环
题目
判断一个单链表是否有环
算法思路
快慢指针
定义两个指针p和q；
让p每次走两步，q每次走一步
当p和q相遇时则说明有环，否则就没有环。
代码实现
/* is_a_ring:判断单链表是否有环 @h：指定的单链表的第一个节点指针 返回值： 1 有环 0 无环 */ int is_a_ring(Node *h) { Node *p = NULL;//fast指针 Node *q = NULL;//slow指针 p = h; q = h; while(p) { p = p->next; if(p == NULL) { break; } p = p->next; q = q->next; if(p == q) { return 1; } } return 0; }
取单链表中间节点的数值
题目
写一个程序，获取链表中间结点的值
例子：
对于奇数结点 返回中间结点值
输入 ：1 2 3 4 5
输出：3
对于偶数结点 返回较小下标的值
输入： 25 69 78 45 96 -21 -47 62
输出：45
算法思路
定义两个指针p和q；
让p每次走两步 q走一步
当p走到链表末尾时 此时q刚好走到链表的中间结点。
代码实现
void get_middle_v(Node *h) { Node *pk = h; //快指针 Node *pm = h; //慢指针 while(1) { if(pk->next == NULL) //快指针已经到了最后一个（奇数个） { printf("%d\n",pm->data); break; } else { pk = pk->next->next; //快指针的下一个是最后一个（偶数个） if(pk == NULL) { printf("%d\n",pm->data); break; } pm = pm->next; } } }
总结
这些题目其实总体难度不高，更重要的是体会其中的算法思路，分类思想，利用好单链表本身的空间余节点取解决问题。
