前一篇文章中記錄了單鏈表的實現(xiàn)和基本操作题禀，在此基礎(chǔ)上该押，本次整理了單鏈表的相關(guān)常見算法題的思路和C語言實現(xiàn)裙犹，留作復(fù)習(xí)備忘伙判，也希望看到此文的大家能有所收獲象对；文中有不對或者不恰當(dāng)?shù)牡胤綒g迎指正；如果你有更好的方法宴抚，歡迎留言交流织盼。
本文完整代碼：鏈表學(xué)習(xí)相關(guān)的筆記和代碼（C 語言）
1.翻轉(zhuǎn)鏈表
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.判斷鏈表中是否存在環(huán)
思路：使用快慢指針，使快指針每次走兩步酱塔，慢指針每次走一步沥邻，如果兩個指針在某個位置相遇，則有環(huán)
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("該鏈表中有環(huán)\n");
return OK;
}
}
printf("該鏈表中沒有環(huán)\n");
return ERROR;
}
3.判斷鏈表中是否存在環(huán)羊娃，有環(huán)的話找到環(huán)的入口
思路:使用快慢指針唐全，使快指針每次走兩步，慢指針每次走一步蕊玷，如果兩個指針在某個位置相遇邮利，則有環(huán),在第一次相遇的時候使快指針返回第一個節(jié)點，同時步長變?yōu)?垃帅，當(dāng)再次相遇必然是在環(huán)入口
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("該鏈表中沒有環(huán)\n");
return ERROR;
}
fast = (*L)->next;//快指針回到起點
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
*loopHead = fast;
return OK;
}
4.返回鏈表的中間節(jié)點
思路:使用快慢指針延届，快指針每次走兩步，慢指針每次走一步贸诚，待快指針走到尾方庭，慢指針正好走到中間節(jié)點
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("鏈表中間結(jié)點的值獲取成功:%d\n", *data);
return OK;
}
5.返回鏈表中倒數(shù)第K個節(jié)點的值
思路:使用兩個指針初始指向第一個節(jié)點，假設(shè)倒數(shù)第K個節(jié)點前有m個節(jié)點酱固，則倒數(shù)第K個節(jié)點即是正數(shù)第m+1個節(jié)點械念，則指針要走m步才能指向第m+1個節(jié)點，由于鏈表長度未知运悲，所以m無法確定,所以轉(zhuǎn)換思路龄减，將倒數(shù)第K轉(zhuǎn)化為正數(shù)第K，則正數(shù)第K個節(jié)點后同樣有m個節(jié)點,所以如此先使一個指針移動到指向正數(shù)第K個節(jié)點班眯，然后兩個指針一起前進(jìn)希停，則當(dāng)前邊的指針走到鏈表末尾烁巫，即指向NULL時，后出發(fā)的指針正好指向要找的倒數(shù)第K個節(jié)點
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;//指向第一個節(jié)點
while (front->next != NULL) {
count ++;
if (count > k) {
back = back->next;
}
front = front->next;
}
if (k > count) {
printf("所求值不在鏈表范圍內(nèi)\n");
return ERROR;
}
*data = back->data;
printf("倒數(shù)第%d個結(jié)點的值獲取成功:%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;
}
未完待續(xù)...
