目錄
題目
1.移除鏈表元素
2.反轉(zhuǎn)鏈表
3.鏈表的中間節(jié)點
4.合并兩個有序鏈表
5.環(huán)形鏈表的約瑟夫問題
解析
題目1：創(chuàng)建新鏈表
題目2：巧用三個指針
題目3：快慢指針
題目4：哨兵位節(jié)點
題目5：環(huán)形鏈表
?文章來源地址http://www.zghlxwxcb.cn/news/detail-860739.html
介紹完了單鏈表，我們這次來說幾個經(jīng)典的題目，本篇的題目銜接下一章雙向鏈表哦~?
題目
1.移除鏈表元素
?文章來源：http://www.zghlxwxcb.cn/news/detail-860739.html
?
2.反轉(zhuǎn)鏈表
?
?
3.鏈表的中間節(jié)點
?
?
4.合并兩個有序鏈表
?
?
5.環(huán)形鏈表的約瑟夫問題
?
?
我們來看看本篇要介紹的解法吧?
解析
這里介紹的解析僅供參考，算法題的實現(xiàn)思路是很多的，小編就不一一詳細介紹了，我們主要介紹小編認為比較好的方法~
題目1：創(chuàng)建新鏈表
思路：找值不為val的節(jié)點，尾插到新鏈表中
?pcur不等于val時，就把節(jié)點放在新鏈表中，新鏈表初始為空鏈表，所以新鏈表的第一個節(jié)點既是newhead也是newtail，放好后pcur往后走，繼續(xù)判斷節(jié)點是否等于val
?pcur所指向的節(jié)點不等于val，把這個節(jié)點尾插到新鏈表里面，newhead不變，newtail往后走，pcur也往后走，繼續(xù)判斷
?此時pcur指向的節(jié)點值為val，pcur再往后走，其余不變
一直到pcur遍歷完原鏈表，此時新鏈表就是去掉所有等于val值的節(jié)點的鏈表
?我們代碼實現(xiàn)一下
首先把結(jié)構(gòu)體類型 struct ListNode 換個名字，方便定義，就換成ListNode
typedef struct ListNode ListNode;?然后在題目給的函數(shù)中進行實現(xiàn)
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
ListNode* newhead, * newtail;//定義新頭節(jié)點、新尾節(jié)點
newhead = newtail = NULL;//新鏈表初始時為空
ListNode* pcur = head;//pcur初始時指向原鏈表首節(jié)點
while ()//開始遍歷鏈表
{
}
}循環(huán)結(jié)束的條件應該是pcur不為NULL，循環(huán)體里面就是剛剛分析的過程
struct ListNode* removeElements(struct ListNode* head, int val)
{
ListNode* newhead, * newtail;//定義新頭節(jié)點、新尾節(jié)點
newhead = newtail = NULL;//新鏈表初始時為空
ListNode* pcur = head;//pcur初始時指向原鏈表首節(jié)點
while (pcur)//開始遍歷鏈表
{
if (pcur->val != val)//找pcur不為val的節(jié)點
{
if (newhead == NULL)//新鏈表為空
{
newhead = newtail = pcur;
}
else//新鏈表不為空
{
newtail->next = pcur;
newtail = newtail->next;
}
}
pcur = pcur->next;//繼續(xù)往后遍歷
}
if(newtail)
newtail->next = NULL;
return newhead;
}?
?
題目2：巧用三個指針
參考思路1：依舊是新創(chuàng)建一個鏈表，遍歷原鏈表，將原鏈表中的節(jié)點采用頭插的形式放在新鏈表中，就可以實現(xiàn)鏈表的翻轉(zhuǎn)
參考思路2：創(chuàng)建3個指針，完成原鏈表的翻轉(zhuǎn)
我們來實現(xiàn)思路2，這個思路一般不太好想
創(chuàng)建3個變量，n1、n2、n3初始時分別指向NULL、節(jié)點1、節(jié)點2
然后讓n2指向n1，n1走到n2的位置，n2走到n3的位置，n3走向下一個節(jié)點
然后再重復上面的步驟，n2指向n1，n1走到n2的位置，n2走到n3的位置，n3走向下一個節(jié)點，
?走到這里的時候n3就不能繼續(xù)走了，n1和n2繼續(xù)走
此時n1就是鏈表的新頭節(jié)點
我們來代碼實現(xiàn)，依舊是重命名一下，把結(jié)構(gòu)體類型 struct ListNode 換個名字，方便定義，換成ListNode
typedef struct ListNode ListNode;然后在題目給的函數(shù)中實現(xiàn)
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
ListNode* n1, * n2, * n3;//創(chuàng)建3個變量
n1 = NULL;//給三個變量賦值
n2 = head;
n3 = n2->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3) //n3為不空時才繼續(xù)往后走
n3 = n3->next;;
}
return n1;
}這是鏈表不為空的情況，那鏈表為空時呢？直接返回?head 就可以了
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL) //空鏈表
return head;
//非空鏈表
ListNode* n1, * n2, * n3;//創(chuàng)建3個變量
n1 = NULL;//給三個變量賦值
n2 = head;
n3 = n2->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3) //n3為不空時才繼續(xù)往后走
n3 = n3->next;;
}
return n1;
}?
?
題目3：快慢指針
這道題的思路也很多，本篇想通過這題介紹一種很妙的方法，快慢指針，快慢指針在之后的很多題中也有很多應用
先來介紹一下快慢指針，slow表示慢指針，fast表示快指針
慢指針slow一次往后走一步，快指針fast一次往后走兩步
fast沒有走到空，繼續(xù)走，slow一次往后走一步，fast一次往后走兩步
fast不能再繼續(xù)往后走，此時slow所指向的節(jié)點就是鏈表的中間節(jié)點，這是節(jié)點個數(shù)為奇數(shù)的情況如果節(jié)點個數(shù)為偶數(shù)個呢？我們來看看
依舊是慢指針slow一次往后走一步，快指針fast一次往后走兩步
此時fast走到空了，不再繼續(xù)往后走，slow所指向的節(jié)點正是第二個中間節(jié)點
這就很簡單了，我們將快慢指針運用到題目中，代碼實現(xiàn)一下
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}這里需要注意：while循環(huán)里面的判斷條件 (fast && fast->next) 中 fast 不能和?fast->next 交換位置，因為如果鏈表結(jié)點個數(shù)是偶數(shù)個時，fast會走到NULL，當fast走到NULL時，while再對fast->next進行判斷，此時可以對空指針解引用嗎？不可以。所以fast->next不可以放在前面。當fast放在前面，此時fast為NULL，直接退出循環(huán)，根本就不會對后面的表達式進行判斷，也就不會出現(xiàn)對空指針解引用的情況。
?
?
題目4：哨兵位節(jié)點
我們先說沒有哨兵位的代碼，哨兵位后面再分析
這題我們先選擇創(chuàng)建新鏈表，遍歷原鏈表，我們定義兩個指針遍歷兩個鏈表
把值小的節(jié)點放在新鏈表中，相等的話隨便放哪個都行，然后讓相應的指針往后走一個
此時L1和L2比較，L1比L2小，把L1的節(jié)點放到新節(jié)點，然后L1往后移
然后再依次向后比較，一直到L1或L2走到NULL為止，遍歷結(jié)果只有兩種情況，要么L1為空，要么L2為空
?我們代碼實現(xiàn)一下，先寫L1的值小于L2的值的時候
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
ListNode* L1 = list1; //遍歷原鏈表
ListNode* L2 = list2;
ListNode* newhead, * newtail; //創(chuàng)建新鏈表
newhead = newtail = NULL;
while (L1 && L2)//循環(huán)遍歷，有一個走到NULL就退出
{
if (L1->val < L2->val)//L1的節(jié)點值小
{
if (newhead == NULL) //新鏈表為空鏈表
{
newhead = newtail = L1;
}
else //新鏈表不為空鏈表
{
newtail->next = L1;//把L1放在新鏈表
newtail = newtail->next;
}
L1 = L1->next;//L1往后走
}
else //L2的節(jié)點值小
{
}
}
}L2小于L1的時候也是類似的，此時while循環(huán)內(nèi)代碼為
while (L1 && L2)//循環(huán)遍歷，有一個走到NULL就退出
{
if (L1->val < L2->val)//L1的節(jié)點值小
{
if (newhead == NULL) //新鏈表為空鏈表
{
newhead = newtail = L1;
}
else //新鏈表不為空鏈表
{
newtail->next = L1; //把L1放在新鏈表
newtail = newtail->next;
}
L1 = L1->next;//L1往后走
}
else //L2的節(jié)點值小
{
if (newhead == NULL) //新鏈表為空鏈表
{
newhead = newtail = L2;
}
else //新鏈表不為空鏈表
{
newtail->next = L2;//把L2放在新鏈表
newtail = newtail->next;
}
L2 = L2->next;//L2往后走
}
}跳出循環(huán)后有兩種情況，要么L1先走到空，要么L2先走到空?，上面的情況就是L1走到空，L2沒有走到空，我們直接把L2拿下來尾插就行了，出while循環(huán)后的代碼如下
//跳出循環(huán)后
if (L2) //L2沒走到空
newtail->next = L2;
if (L1) //L1沒走到空
newtail->next = L1;
return newhead;我們還需要處理一下空鏈表的情況，空鏈表的情況代碼放在函數(shù)體最前面
//空鏈表的情況
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;?
我們會發(fā)現(xiàn)代碼重復的部分很多，我們?nèi)绾稳?yōu)化它？首先要找為什么會重復
我們向操作系統(tǒng)申請一個空間，這個空間不存有效數(shù)據(jù)
newhead = newtail = (ListNode*)malloc(sizeof(ListNode));此時鏈表也改變了
?所以現(xiàn)在的代碼就變了，返回值也變了
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//空鏈表的情況
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
ListNode* L1 = list1; //遍歷原鏈表
ListNode* L2 = list2;
ListNode* newhead, * newtail; //創(chuàng)建新鏈表
newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
while (L1 && L2)//循環(huán)遍歷，有一個走到NULL就退出
{
if (L1->val < L2->val)//L1的節(jié)點值小
{
newtail->next = L1; //把L1放在新鏈表
newtail = newtail->next;
L1 = L1->next;//L1往后走
}
else //L2的節(jié)點值小
{
newtail->next = L2;//把L2放在新鏈表
newtail = newtail->next;
L2 = L2->next;//L2往后走
}
}
//跳出循環(huán)后
if (L2) //L2沒走到空
newtail->next = L2;
if (L1) //L1沒走到空
newtail->next = L1;
return newhead->next;
}我們malloc的空間要記得釋放，所以可以在return上面加三排代碼，而且return的值也要改一下
ListNode* ret = newhead->next;//存newhead->next的值
free(newhead);
newhead = NULL;
return ret;所以這里的頭節(jié)點就是哨兵位
?
題目5：環(huán)形鏈表
我們先介紹一下約瑟夫問題的歷史背景
據(jù)說著名猶太 歷史學家 Josephus（ 弗拉維奧·約瑟夫斯 ）有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。約瑟夫?qū)⒆约汉退呐笥寻才旁?6和31個位置，于是逃脫了這場死亡游戲
來看一下環(huán)形鏈表
我們畫個圖簡單介紹一下
此時把3節(jié)點去掉，繼續(xù)從下一個存在的節(jié)點開始報數(shù)
再把節(jié)點1去掉，繼續(xù)從下一個存在的節(jié)點開始報數(shù)
把節(jié)點5去掉，現(xiàn)在留下兩個節(jié)點，如果約瑟夫和他的朋友想要存活，就要站在2或4的位置
?
那么這道題就是類似，不過是留下一個節(jié)點
拿5個節(jié)點，報數(shù)為2舉例
?
最后就留下了節(jié)點3
代碼中我們?nèi)绾畏治瞿?？看下圖。
數(shù)1之后數(shù)2，此時pcur后移，prev后移
pcur所指向的節(jié)點數(shù)到了2，要銷毀pcur所指的節(jié)點，銷毀的時候先讓prev的next指針指向pcur的next
然后把pcur指向的節(jié)點銷毀，并且讓pcur指向下一個節(jié)點，也就是prev的next指針指向的位置
然后繼續(xù)數(shù)數(shù)，從1開始
然后就是重復步驟，當只剩下兩個節(jié)點時，分析一下
pcur報數(shù)為2，刪掉5這個節(jié)點，要先讓prev的next指針指向pcur的next，也就是節(jié)點3此時自己指向自己
然后再銷毀節(jié)點5，此時pcur也指向節(jié)點3?
大概分析就是這樣，我們代碼實現(xiàn)一下
先寫一個創(chuàng)建節(jié)點的函數(shù)
typedef struct ListNode ListNode;
ListNode* BuyNode(int x)//創(chuàng)建節(jié)點
{
ListNode* node=(ListNode*)malloc(sizeof(ListNode));
if(node==NULL)
{
exit(1);
}
node->val = x;
node->next = NULL;
return node;
}然后寫帶環(huán)鏈表的函數(shù)
ListNode* CreatCircle(int n)//創(chuàng)建帶環(huán)鏈表
{
ListNode* phead=BuyNode(1);//先創(chuàng)建頭節(jié)點
ListNode* ptail=phead;
for (int i = 2; i <= n; i++)
{
ptail->next=BuyNode(i);//尾插新節(jié)點
ptail = ptail->next;
}
ptail->next=phead;//頭尾相連，變成循環(huán)鏈表
return ptail;
}然后在ysf函數(shù)中實現(xiàn)
int ysf(int n, int m )
{
ListNode* prev = CreatCircle(n);//環(huán)形鏈表尾節(jié)點由prev接收
ListNode* pcur = prev->next;//頭節(jié)點由pcur接收
int count = 1;
while (pcur->next != pcur)
{
if(count == m) //需要銷毀節(jié)點
{
prev->next = pcur->next;
free(pcur);
pcur = prev->next;
count = 1;//重新計數(shù)
}
else //不用銷毀節(jié)點
{
prev = pcur;
pcur = pcur->next;
count++;
}
}
return pcur->val;
}?
?這次分享就到這里了，拜拜~
?
?
?
到了這里，關于【數(shù)據(jù)結(jié)構(gòu)】單鏈表經(jīng)典算法題的巧妙解題思路的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
