随便的配图
前一篇文章中记录了单链表的实现和基本操作，在此基础上，本次整理了单链表的相关常见算法题的思路和C语言实现，留作复习备忘，也希望看到此文的大家能有所收获；文中有不对或者不恰当的地方欢迎指正；如果你有更好的方法，欢迎留言交流。
本文完整代码：链表学习相关的笔记和代码（C 语言）
1.翻转链表
Status reserveLinkList(LinkList *L)
{
if (*L == NULL) {
printf("链表没有初始化");
return ERROR;
}
if ((*L)->next == NULL) {
printf("链表为空");
return ERROR;
}
LinkList p, pPro, pNext;
p = (*L)->next;
pNext = p->next;
pPro = NULL;
while (pNext != NULL) {
p->next = pPro;
pPro = p;
p = pNext;
pNext = pNext->next;
}
p->next = pPro;
pPro = p;
(*L)->next = pPro;
pPro = p = NULL;
return OK;
}
2.判断链表中是否存在环
思路：使用快慢指针，使快指针每次走两步，慢指针每次走一步，如果两个指针在某个位置相遇，则有环
Status checkExistLoop(LinkList *L)
{
if (*L == NULL) {
printf("链表没有初始化!\n");
return ERROR;
}
if ((*L)->next == NULL) {
printf("链表为空");
return ERROR;
}
LinkList fast, slow;
slow = fast = (*L)->next;
while (slow != NULL && fast != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
printf("该链表中有环\n");
return OK;
}
}
printf("该链表中没有环\n");
return ERROR;
}
3.判断链表中是否存在环，有环的话找到环的入口
思路:使用快慢指针，使快指针每次走两步，慢指针每次走一步，如果两个指针在某个位置相遇，则有环,在第一次相遇的时候使快指针返回第一个节点，同时步长变为1，当再次相遇必然是在环入口
Status getLoopHead(LinkList *L, LinkList *loopHead)
{
if (*L == NULL) {
printf("链表没有初始化!\n");
return ERROR;
}
if ((*L)->next == NULL) {
printf("链表为空");
return ERROR;
}
LinkList fast, slow;
slow = fast = (*L)->next;
while (slow != NULL && fast != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
if (slow != fast) {
printf("该链表中没有环\n");
return ERROR;
}
fast = (*L)->next;//快指针回到起点
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
*loopHead = fast;
return OK;
}
4.返回链表的中间节点
思路:使用快慢指针，快指针每次走两步，慢指针每次走一步，待快指针走到尾，慢指针正好走到中间节点
Status getMidNode(LinkList *L, ElemType *data)
{
if (*L == NULL) {
printf("链表没有初始化!\n");
return ERROR;
}
if ((*L)->next == NULL) {
printf("链表为空");
return ERROR;
}
LinkList front, back;
front = back = (*L)->next;
while (front != NULL && front->next != NULL) {
front = front->next->next;
back = back->next;
}
*data = back->data;
printf("链表中间结点的值获取成功:%d\n", *data);
return OK;
}
5.返回链表中倒数第K个节点的值
思路:使用两个指针初始指向第一个节点，假设倒数第K个节点前有m个节点，则倒数第K个节点即是正数第m+1个节点，则指针要走m步才能指向第m+1个节点，由于链表长度未知，所以m无法确定,所以转换思路，将倒数第K转化为正数第K，则正数第K个节点后同样有m个节点,所以如此先使一个指针移动到指向正数第K个节点，然后两个指针一起前进，则当前边的指针走到链表末尾，即指向NULL时，后出发的指针正好指向要找的倒数第K个节点
Status getCountDownK(LinkList *L, int k, ElemType *data)
{
if (*L == NULL) {
printf("链表没有初始化!\n");
return ERROR;
}
if ((*L)->next == NULL) {
printf("链表为空");
return ERROR;
}
LinkList front, back;
int count = 1;
front = back = (*L)->next;//指向第一个节点
while (front->next != NULL) {
count ++;
if (count > k) {
back = back->next;
}
front = front->next;
}
if (k > count) {
printf("所求值不在链表范围内\n");
return ERROR;
}
*data = back->data;
printf("倒数第%d个结点的值获取成功:%d\n", k, *data);
return OK;
}
6.倒序打印整个链表(递归)
Status printLinkListReserve(LinkList head)
{
if (head != NULL) {
if (head->next != NULL) {
printLinkListReserve(head->next);
}
}
printf("链表倒序输出:%d\n",head->data);
return OK;
}
未完待续...
