C語言實(shí)題講解快速掌握單鏈表上

第C語言實(shí)題講解快速掌握單鏈表上目錄1、移除鏈表元素2、反轉(zhuǎn)鏈表3、鏈表的中間節(jié)點(diǎn)4、鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)5、合并兩個(gè)有序鏈表6、鏈表分割

1、移除鏈表元素

鏈接直達(dá)：

移除鏈表元素

題目：

思路：

此題要綜合考慮多種情況，常規(guī)情況就如同示例1，有多個(gè)節(jié)點(diǎn)，并且val不連續(xù)，但是非常規(guī)呢？當(dāng)val連續(xù)呢？當(dāng)頭部就是val呢？所以要分類討論

常規(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ī)處理即可。

代碼如下：

structListNode*removeElements(structListNode*head,intval){

structListNode*cur=head;

structListNode*prev=NULL;

while(cur)

if(cur-val!=val)

prev=cur;

cur=cur-next;

else

structListNode*next=cur-next;

if(prev==NULL)

free(cur);

cur=next;

head=next;

else

prev-next=cur-next;

free(cur);

cur=prev-next;

returnhead;

}

2、反轉(zhuǎn)鏈表

鏈接直達(dá)：

反轉(zhuǎn)鏈表

題目：

思路：

法一：三指針翻轉(zhuǎn)方向

定義三個(gè)指針n1，n2，n3分別用來指向NULL，第一個(gè)數(shù)據(jù)，第二個(gè)數(shù)據(jù)。讓n2的next指向n1，把n2賦給n1，再把n3賦給n2，再執(zhí)行n3=n3-next的操作，接下來重復(fù)上述操作，直到n2指向空即可。但是要注意，要先判斷該鏈表是否為NULL，如果是，則返回NULL，此外，還要保證當(dāng)n3為空時(shí)就不要?jiǎng)恿?，直接把n3賦給n2即可。

代碼如下：

structListNode*reverseList(structListNode*head){

if(head==NULL)

returnNULL;

structListNode*n1=NULL;

structListNode*n2=head;

structListNode*n3=n2-next;

while(n2)

n2-next=n1;

n1=n2;

n2=n3;

if(n3)

n3=n3-next;

returnn1;

}

法二：頭插

此法就需要再創(chuàng)建一個(gè)鏈表了，創(chuàng)建一個(gè)新的頭部newhead指向NULL，再定義一個(gè)指針cur指向原鏈表第一個(gè)數(shù)據(jù)，注意還得定義一個(gè)指針next指向cur的下一個(gè)節(jié)點(diǎn)。遍歷原鏈表，把節(jié)點(diǎn)取下來頭插到newhead所在的鏈表。每次更新newhead賦給cur，如圖所示：

代碼如下：

structListNode*reverseList(structListNode*head){

if(head==NULL)

returnNULL;

structListNode*cur=head;

structListNode*next=cur-next;

structListNode*newhead=NULL;

while(cur)

cur-next=newhead;

newhead=cur;

cur=next;

if(next)

next=next-next;

returnnewhead;

}

3、鏈表的中間節(jié)點(diǎn)

鏈接直達(dá)：

鏈表的中間節(jié)點(diǎn)

題目：

思路：

快慢指針

這道題要注意奇偶數(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)

代碼如下：

structListNode*middleNode(structListNode*head){

structListNode*slow=head;

structListNode*fast=head;

while(fastfast-next)

slow=slow-next;

fast=fast-next-next;

returnslow;

}

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)檫@樣的話slow和fast的差距始終是k個(gè)，當(dāng)fast走到空時(shí)結(jié)束。此題同樣可以走k-1步，不過當(dāng)fast走到尾部時(shí)結(jié)束，也就是fast的下一個(gè)節(jié)點(diǎn)指向空時(shí)結(jié)束，都一樣。先拿走k步舉例，如圖所示：

代碼如下：

structListNode*FindKthToTail(structListNode*pListHead,intk){

//writecodehere

structListNode*fast=pListHead;

structListNode*slow=pListHead;

while(k--)

//if判斷，防止k大于鏈表的長(zhǎng)度

if(fast==NULL)

returnNULL;

fast=fast-next;

while(fast)

fast=fast-next;

slow=slow-next;

returnslow;

}

5、合并兩個(gè)有序鏈表

鏈接直達(dá)：

合并兩個(gè)有序鏈表

題目：

思路：

法一：歸并（取小的尾插）---帶頭節(jié)點(diǎn)

假設(shè)新鏈表的頭叫head并指向NULL，還需要定義一個(gè)指針tail來方便后續(xù)的找尾，依次比較list1和list2節(jié)點(diǎn)的值，把小的放到新鏈表head上，并更新tail，再把list1或list2更新一下。當(dāng)list1和list2兩個(gè)鏈表中一個(gè)走到空時(shí)，直接把剩下的鏈表所有剩下的元素拷進(jìn)去即可

代碼如下：

structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){

//檢查list1或list2一開始就為NULL的情況

if(list1==NULL)

returnlist2;

if(list2==NULL)

returnlist1;

structListNode*head=NULL;

structListNode*tail=head;

while(list1list2)

if(list1-vallist2-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;

returnhead;

}

法二：哨兵位的頭節(jié)點(diǎn)

解釋下帶頭節(jié)點(diǎn)：

比如說同樣一個(gè)鏈表存1，2，3。不帶頭節(jié)點(diǎn)只有這三個(gè)節(jié)點(diǎn)，head指向1。而帶頭節(jié)點(diǎn)的同樣存3個(gè)值，不過有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ì)方便不少。和上述思路一樣，取小的下來尾插，直接鏈接到tail后面即可。但是要注意返回的時(shí)候要返回head的next，因?yàn)轭}目給的鏈表是不帶頭的，而head本身指向的就是那個(gè)頭，所以要返回下一個(gè)。

代碼如下：

structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){

structListNode*head=NULL,*tail=NULL;

head=tail=(structListNode*)malloc(sizeof(structListNode));

head-next=NULL;

while(list1list2)

if(list1-vallist2-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;

structListNode*list=head-next;

free(head);

head=NULL

returnlist;

}

6、鏈表分割

鏈接直達(dá)：

鏈表分割

題目：

思路：

定義兩個(gè)鏈表lesshead和greaterhead。遍歷原鏈表，把x的插入到鏈表1，把x的插入到鏈表2，最后再把鏈表1和鏈表2鏈接起來。在定義兩個(gè)尾指針以跟進(jìn)鏈表1和2新增元素

代碼如下：

classPartition{

public:

ListNode*partition(ListNode*pHead,intx){

//writecodehere

structListNode*lessHead,*lessTail,*greaterHead,*greaterTail;

lessHead=lessTail=(structListNode*)malloc(sizeof(structListNode));

greaterHead=greaterTail=(structListNode*)malloc(sizeof(structListNode));

lessTail-next=greaterTail-next=NULL;

structListNode*cur=pHead;

while(cur)

if(cur-valx)

lessTail-next=cur;

lessTail=lessTail-