C語(yǔ)言實(shí)題講解快速掌握單鏈表上
1、移除鏈表元素
鏈接直達(dá)：
題目：
思路：
此題要綜合考慮多種情況，常規(guī)情況就如同示例1，有多個(gè)節(jié)點(diǎn)，并且val不連續(xù)，但是非常規(guī)呢？當(dāng)val連續(xù)呢？當(dāng)頭部就是val呢？所以要分類(lèi)討論
常規(guī)情況：
需要定義兩個(gè)指針prev和cur，cur指向第一個(gè)數(shù)據(jù)，prev指向cur的前一個(gè)。依次遍歷cur指向的數(shù)據(jù)是否為val，若是，則把prev的下一個(gè)節(jié)點(diǎn)指向cur的下一個(gè)節(jié)點(diǎn)上，cur=cur->next，prev跟著cur一起走，直到cur走到NULL
連續(xù)val：
當(dāng)我們仔細(xì)觀察下，不難發(fā)現(xiàn)，在常規(guī)情況下是可以解決連續(xù)val的，但是頭部val就不可了
頭部val：
此時(shí)除了剛才定義的兩個(gè)指針prev和cur外，還要有個(gè)head指向頭部，當(dāng)頭部是val時(shí)，將cur指向下一個(gè)位置，head跟著一起動(dòng)，直到cur指向的數(shù)據(jù)不為val時(shí)，將head賦給prev。此時(shí)剩余的就按常規(guī)處理即可。
代碼如下：
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode*cur=head;
struct ListNode*prev=NULL;
while(cur)
{
if(cur->val!=val)
{
prev=cur;
cur=cur->next;
}
else
{
struct ListNode*next=cur->next;
if(prev==NULL)
{
free(cur);
cur=next;
head=next;
}
else
{
prev->next=cur->next;
free(cur);
cur=prev->next;
}
}
}
return head;
}2、反轉(zhuǎn)鏈表
鏈接直達(dá)：
題目：
思路：
法一：三指針?lè)D(zhuǎn)方向
定義三個(gè)指針n1，n2，n3分別用來(lái)指向NULL，第一個(gè)數(shù)據(jù)，第二個(gè)數(shù)據(jù)。讓n2的next指向n1，把n2賦給n1，再把n3賦給n2，再執(zhí)行n3=n3->next的操作，接下來(lái)重復(fù)上述操作，直到n2指向空即可。但是要注意，要先判斷該鏈表是否為NULL，如果是，則返回NULL，此外，還要保證當(dāng)n3為空時(shí)就不要?jiǎng)恿?，直接把n3賦給n2即可。
代碼如下：
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
{
return NULL;
}
struct ListNode*n1=NULL;
struct ListNode*n2=head;
struct ListNode*n3=n2->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
{
n3=n3->next;
}
}
return n1;
}法二：頭插
此法就需要再創(chuàng)建一個(gè)鏈表了，創(chuàng)建一個(gè)新的頭部newhead指向NULL，再定義一個(gè)指針cur指向原鏈表第一個(gè)數(shù)據(jù)，注意還得定義一個(gè)指針next指向cur的下一個(gè)節(jié)點(diǎn)。遍歷原鏈表，把節(jié)點(diǎn)取下來(lái)頭插到newhead所在的鏈表。每次更新newhead賦給cur，如圖所示：
代碼如下：
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL)
{
return NULL;
}
struct ListNode*cur=head;
struct ListNode*next=cur->next;
struct ListNode*newhead=NULL;
while(cur)
{
cur->next=newhead;
newhead=cur;
cur=next;
if(next)
{
next=next->next;
}
}
return newhead;
}3、鏈表的中間節(jié)點(diǎn)
鏈接直達(dá)：
題目：
思路：
快慢指針
這道題要注意奇偶數(shù)，如果為奇數(shù)，如示例1，那么中間節(jié)點(diǎn)值就是3，反之偶數(shù)如示例2，返回第二個(gè)中間節(jié)點(diǎn)。此題我們定義兩個(gè)指針slow和fast都指向第一個(gè)數(shù)據(jù)的位置，區(qū)別在于讓slow一次走1步，fast一次走2步。當(dāng)fast走到尾指針時(shí)，slow就是中間節(jié)點(diǎn)
代碼如下：
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*slow=head;
struct ListNode*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}4、鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
鏈接直達(dá)：
鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
題目：
思路：
快慢指針
定義兩個(gè)指針slow和fast，讓fast先走k步，再讓slow和fast同時(shí)走，當(dāng)fast走到尾部時(shí)，slow就是倒數(shù)第k個(gè)，因?yàn)檫@樣的話(huà)slow和fast的差距始終是k個(gè)，當(dāng)fast走到空時(shí)結(jié)束。此題同樣可以走k-1步，不過(guò)當(dāng)fast走到尾部時(shí)結(jié)束，也就是fast的下一個(gè)節(jié)點(diǎn)指向空時(shí)結(jié)束，都一樣。先拿走k步舉例，如圖所示：
代碼如下：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
struct ListNode*fast=pListHead;
struct ListNode*slow=pListHead;
while(k--)
{
//if判斷，防止k大于鏈表的長(zhǎng)度
if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}5、合并兩個(gè)有序鏈表
鏈接直達(dá)：
題目：
思路：
法一：歸并（取小的尾插）--- 帶頭節(jié)點(diǎn)
假設(shè)新鏈表的頭叫head并指向NULL，還需要定義一個(gè)指針tail來(lái)方便后續(xù)的找尾，依次比較list1和list2節(jié)點(diǎn)的值，把小的放到新鏈表head上，并更新tail，再把list1或list2更新一下。當(dāng)list1和list2兩個(gè)鏈表中一個(gè)走到空時(shí)，直接把剩下的鏈表所有剩下的元素拷進(jìn)去即可
代碼如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//檢查list1或list2一開(kāi)始就為NULL的情況
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
struct ListNode*head=NULL;
struct ListNode*tail=head;
while(list1&&list2)
{
if(list1->val<list2->val)
{
if(tail==NULL)
{
head=tail=list1;
}
else
{
tail->next=list1;
tail=list1;
}
list1=list1->next;
}
else
{
if(tail==NULL)
{
head=tail=list2;
}
else
{
tail->next=list2;
tail=list2;
}
list2=list2->next;
}
}
//當(dāng)list1和list2其中一個(gè)走到空的情況
if(list1==NULL)
{
tail->next=list2;
}
else
{
tail->next=list1;
}
return head;
}法二：哨兵位的頭節(jié)點(diǎn)
解釋下帶頭節(jié)點(diǎn)：
比如說(shuō)同樣一個(gè)鏈表存1，2，3。不帶頭節(jié)點(diǎn)只有這三個(gè)節(jié)點(diǎn)，head指向1。而帶頭節(jié)點(diǎn)的同樣存3個(gè)值，不過(guò)有4個(gè)節(jié)點(diǎn)，head指向頭部這個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)不存儲(chǔ)有效數(shù)據(jù)
帶頭結(jié)點(diǎn)有如下好處，不用判斷head和tail是否為空了，也不用判斷l(xiāng)ist1和list2是否為空了，會(huì)方便不少。和上述思路一樣，取小的下來(lái)尾插，直接鏈接到tail后面即可。但是要注意返回的時(shí)候要返回head的next，因?yàn)轭}目給的鏈表是不帶頭的，而head本身指向的就是那個(gè)頭，所以要返回下一個(gè)。
代碼如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* head = NULL, * tail = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next = NULL;
while (list1 && list2)
{
if (list1->val < list2->val)
{
tail->next = list1;
tail = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = list2;
list2 = list2->next;
}
}
//當(dāng)list1和list2其中一個(gè)走到空的情況
if (list1 == NULL)
{
tail->next = list2;
}
else
{
tail->next = list1;
}
struct ListNode* list = head->next;
free(head);
head = NULL
return list;
}6、鏈表分割
鏈接直達(dá)：
題目：
思路：
定義兩個(gè)鏈表lesshead和greaterhead。遍歷原鏈表，把 < x 的插入到鏈表1，把 > x 的插入到鏈表2，最后再把鏈表1和鏈表2鏈接起來(lái)。在定義兩個(gè)尾指針以跟進(jìn)鏈表1和2新增元素
代碼如下：
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
lessTail->next = greaterTail->next = NULL;
struct ListNode* cur = pHead;
while (cur)
{
if (cur->val < x)
{
lessTail->next = cur;
lessTail = lessTail->next;
}
else
{
greaterTail->next = cur;
greaterTail = greaterTail->next;
}
cur = cur->next;
}
//合并
lessTail->next = greaterHead->next;
greaterTail->next = NULL;
struct ListNode* list = lessHead->next;
free(lessHead);
free(greaterHead);
return list;
}
};到此這篇關(guān)于C語(yǔ)言實(shí)題講解快速掌握單鏈表上的文章就介紹到這了,更多相關(guān)C語(yǔ)言 單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言詳細(xì)解析有符號(hào)數(shù)與無(wú)符號(hào)數(shù)的表示
我們知道，在C語(yǔ)言中存在無(wú)符號(hào)數(shù)和有符號(hào)數(shù)，但是對(duì)于計(jì)算機(jī)而言，其本身并不區(qū)別有符號(hào)數(shù)和無(wú)符號(hào)數(shù)，因?yàn)樵谟?jì)算機(jī)里面都是O或者1，但是在我們的實(shí)際使用中有時(shí)候需要使用有符號(hào)數(shù)來(lái)表示一個(gè)整數(shù)，因此我們規(guī)定，當(dāng)最高位為1的時(shí)，表示為負(fù)數(shù)，最高位為0時(shí)，表示為正數(shù)2022-04-04
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)哈夫曼編碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
C++深入探究類(lèi)與對(duì)象之友元與運(yùn)算符重載
友元就是讓一個(gè)函數(shù)或者類(lèi)，訪(fǎng)問(wèn)另一個(gè)類(lèi)中的私有成員；打個(gè)比方，這相當(dāng)于是說(shuō)：朋友是值得信任的，所以可以對(duì)他們公開(kāi)一些自己的隱私，運(yùn)算符重載的實(shí)質(zhì)就是函數(shù)重載或函數(shù)多態(tài)，運(yùn)算符重載是一種形式的C++多態(tài)，目的在于讓人能夠用同名的函數(shù)來(lái)完成不同的基本操作2022-04-04
Qt數(shù)據(jù)庫(kù)相關(guān)應(yīng)用開(kāi)發(fā)總結(jié)
這篇文章主要為大家介紹了在Qt數(shù)據(jù)庫(kù)應(yīng)用開(kāi)發(fā)中的一些經(jīng)驗(yàn)總結(jié)，以及一些組件的使用介紹。文中的示例代碼講解詳細(xì)，需要的可以參考一下2022-02-02
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)哈夫曼樹(shù)的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
用c++實(shí)現(xiàn)將文本每個(gè)單詞首字母轉(zhuǎn)換為大寫(xiě)
本篇文章是對(duì)用c++實(shí)現(xiàn)將文本每個(gè)單詞首字母轉(zhuǎn)換為大寫(xiě)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
大家好，本篇文章主要講的是C語(yǔ)言中自定義類(lèi)型詳解，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下2022-01-01
C++成員函數(shù)如何當(dāng)作回調(diào)函數(shù)同時(shí)傳遞this指針
這篇文章主要介紹了C++成員函數(shù)如何當(dāng)作回調(diào)函數(shù)同時(shí)傳遞this指針，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
線(xiàn)程的主要優(yōu)勢(shì)在于，能夠通過(guò)全局變量來(lái)共享信息。不過(guò)，這種便捷的共享是有代價(jià)的：必須確保多個(gè)線(xiàn)程不會(huì)同時(shí)修改同一變量，或者某一線(xiàn)程不會(huì)讀取正由其他線(xiàn)程修改的變量。為了防止出現(xiàn)線(xiàn)程某甲試圖訪(fǎng)?問(wèn)一共享變量時(shí)，線(xiàn)程某乙正在對(duì)其進(jìn)行修改。引入了互斥量2022-05-05
C語(yǔ)言sizeof和strlen的指針和數(shù)組面試題詳解
strlen是函數(shù)，字符串長(zhǎng)度，不包括停止符。而sizeof則是內(nèi)存塊的大小，包括停止符。數(shù)組是一種數(shù)據(jù)類(lèi)型，數(shù)據(jù)類(lèi)型的本質(zhì)就是固定大小，內(nèi)存塊的別名?？梢杂胹izeof（）一般都是數(shù)據(jù)類(lèi)型2022-04-04