前言
還不清楚鏈表的碼喵們可以看看前篇關(guān)于鏈表的詳解
1.鏈表面試題
既然已經(jīng)懂得了鏈表該如何實(shí)現(xiàn)，那么現(xiàn)在就趁熱打鐵開(kāi)始練習(xí)！這里給碼喵們整理了相對(duì)不錯(cuò)的一些OJ題來(lái)練習(xí)
1. 刪除鏈表中等于給定值 val 的所有結(jié)點(diǎn)。
?力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)
思路：遍歷整個(gè)表，訪問(wèn)每個(gè)表的值并且刪除再將next的指針指向下一個(gè)節(jié)點(diǎn)
此題比較簡(jiǎn)單，但是有幾個(gè)要點(diǎn)來(lái)考慮：
-
如果第一位是需要?jiǎng)h除的數(shù)
-
執(zhí)行刪除時(shí)要如何保存此值的地址來(lái)進(jìn)行空間釋放
-
等于val值執(zhí)行刪除
-
不等于val的值執(zhí)行向下遍歷
附原代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode *tail=head;
struct ListNode *prev=NULL; //用于記錄節(jié)點(diǎn)在free掉的時(shí)候避免找不到
while(tail!=NULL) //不為尾節(jié)點(diǎn)向后遍歷
{
if(tail->val == val) //如果第一位是需要?jiǎng)h除的數(shù)
{
if(tail==head)
{
head=tail->next;
free(tail);
tail = head;
}
else //執(zhí)行刪除節(jié)點(diǎn)，并且free掉空間避免空指針或溢出
{
prev->next = tail->next;
free(tail);
tail = prev->next;
}
}
else
{
prev = tail;
tail=tail->next;
}
}
return head;
}2. 反轉(zhuǎn)一個(gè)單鏈表。
力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)
本題有些難度，但是掌握好方法后類似的題就能做到運(yùn)籌帷幄（決勝千里之外）
萬(wàn)事開(kāi)頭難，掌握方法微妙，剛開(kāi)始我做這題的時(shí)候想的是把他變成一個(gè)循環(huán)指針然后再標(biāo)記頭指針并且實(shí)現(xiàn)反轉(zhuǎn)，不知道這樣的辦法大家有沒(méi)有試過(guò)哈哈，現(xiàn)在我們來(lái)用更簡(jiǎn)單的方法吧。
我們來(lái)指定三個(gè)指針，前兩個(gè)指針用于將前一個(gè)的指針記錄并且連接，第三個(gè)指針負(fù)責(zé)向后遍歷直到為空
方法1
定義三個(gè)指針
n1滯空用于將頭指針變成新鏈表的尾指針，所以滯空
n2 ,n3向后遍歷
首先我們讓n2的下一個(gè)結(jié)點(diǎn)指向n1,實(shí)現(xiàn)第二和第一個(gè)節(jié)點(diǎn)的相連，再讓n2=n3改變n2的地址，再讓n3向下一個(gè)節(jié)點(diǎn)移動(dòng)
n3再向下一個(gè)節(jié)點(diǎn)移動(dòng)，之后循環(huán)到n2為空地址，就完成了所有節(jié)點(diǎn)的反轉(zhuǎn)了。
注意要點(diǎn)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-837210.html
- 鏈表初始值為空要怎么處理
- 鏈表的n2最終到哪里才算結(jié)束反轉(zhuǎn)
- 指針n3的下一個(gè)節(jié)點(diǎn)若為空怎么辦（不能賦值否則會(huì)越界）
附原代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode * n1,*n2,*n3;
n1=NULL;
n2=head;
if(n2)
n3=n2->next;
while(n2)
{
n2->next = n1;
n1=n2;
n2 = n3;
if(n3)
n3=n3->next;
}
return n1;
}方法2
我們可以采用頭插到新表的方法實(shí)現(xiàn)反轉(zhuǎn)，頭插進(jìn)NULL的表，每次插入的數(shù)據(jù)就是原表按順序遍歷。
定義一個(gè)新表為空
再讓原表的cur的下一個(gè)節(jié)點(diǎn)指向newhead，這樣就實(shí)現(xiàn)了頭插，然后我們?cè)俣x一個(gè)指針來(lái)記錄原cur的下一個(gè)節(jié)點(diǎn)，最后再將newhead指向cur,cur指向下一個(gè)節(jié)點(diǎn)next.
循環(huán)這個(gè)操作，直到cur為NULL
返回newhead
附原代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur=head;
struct ListNode* newhead = NULL;
while(cur)
{
struct ListNode* next=cur->next;
cur->next = newhead; //指向新節(jié)點(diǎn)
newhead = cur;
cur = next;
}
return newhead;
}
3. 給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。
力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)
這就要運(yùn)用上非常巧妙的方法了，既然上一題我們用到了三個(gè)指針，這道題我們也用指針來(lái)做，但是只用兩個(gè)指針就好
方法
我們定義兩個(gè)指針都在頭節(jié)點(diǎn)向后遍歷，但是一個(gè)節(jié)點(diǎn)一次走一步，一個(gè)節(jié)點(diǎn)一次走兩步
當(dāng)tail走到最后的節(jié)點(diǎn)時(shí)，head節(jié)點(diǎn)剛好返回的就是中間值。
注意要點(diǎn)：
- tail走兩步，head走一步，返回head的地址就是中間的地址
- 如果tail走到尾要怎么處理
附源代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* tail = head;
while(tail->next)
{
head=head->next;
tail=tail->next;
if(tail->next==NULL)
{
//head=head->next;
}
else
tail=tail->next;
}
return head;
// struct ListNode* tail = head;
// int count=0;
// while(tail->next)
// {
// count++;
// tail = tail->next;
// }
// if(count%2!=0)
// {
// count=(count+1)/2;
// }
// else
// count/=2;
// while(count--)
// {
// head=head->next;
// }
// return head;
}4. 輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。?
鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)_牛客題霸_?？途W(wǎng)
此題是上一題的升級(jí)版，方法相似，上一題是相對(duì)移動(dòng)，本體是相對(duì)距離再移動(dòng)
方法
這次我們定義兩個(gè)指針，一個(gè)first指針先向前走k步，之后在first和tail指針一起向前走，直到first指針走到結(jié)尾，返回tail指針
注意要點(diǎn)
- first指針走到尾該如何處理
- 空的鏈表該如何處理
- k等于鏈表的長(zhǎng)度該返回什么值（返回第一個(gè)節(jié)點(diǎn)）
- k大于鏈表的長(zhǎng)度該返回什么值（不是我想思考，是nt牛客的測(cè)試用例真有這幾點(diǎn)，吃飽撐著）
附源代碼
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pListHead ListNode類
* @param k int整型
* @return ListNode類
*/
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
if (pListHead == NULL) //鏈表為空直接返回NULL
{
return pListHead;
}
struct ListNode* first = pListHead;
struct ListNode* tail = pListHead;
while (first->next) //直到first走到尾
{
while (k > 0 && first->next) //k沒(méi)減到0并且first還沒(méi)走到尾進(jìn)入循環(huán)
{
k--; //這里用k自減1來(lái)進(jìn)行k次循環(huán)的實(shí)現(xiàn)（k=0側(cè)不執(zhí)行）
first = first->next;
//if (first->next == NULL && k > 0)
//{
// return NULL;
//}
}
if (first->next == NULL&&k==1) //當(dāng)k減到1并且first已經(jīng)走到尾
{
return tail; //我們就可以直接返回tail的值，這就是返回第一個(gè)節(jié)點(diǎn)
}
else if(k>1) //如果first到達(dá)尾，并且k還大于1，那就是k大于整個(gè)鏈表長(zhǎng)度的情況
{
return NULL; //直接返回NULL
}
tail = tail->next; //tail向下走一步
first = first->next; //frist向下走一步
}
//tail=tail->next;
return tail->next;
}
// int count = k;
// while(first->next)
// {
// first=first->next;
// }
// int len = count;
// while(tail->next)
// {
// while(len--)
// {
// tail=tail->next;
// }
// if(tail!=first)
// {
// len = count;
// }
// else
// {
// return pListHead->next;
// }
// pListHead = tail;
// }
// return 0;
// write code here5. 將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有 結(jié)點(diǎn)組成的。
力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)
方法
照?qǐng)D來(lái)看，我們可以很明顯的知道我們可以把新的數(shù)據(jù)放入“新的“鏈表，這里的引號(hào)，意思是這種合并的題目，我們可以不創(chuàng)建新的空間，因?yàn)殒湵淼奶匦?，就是每個(gè)都是一塊獨(dú)立的空間，而我們就可以把這些表重新”排序“使之形成一個(gè)新的鏈表，而這里的排序方法就是：比較較小值，尾插入新表中。
新建兩個(gè)鏈表
當(dāng)新表為空時(shí)，將較小值（list1）的地址直接賦值，并且更新list1使之向后走，這里因?yàn)閘ist1、list2相等，所以隨便取一個(gè)就行。
依此類推，list2、list1對(duì)比時(shí)，list2較小，將list2賦值list3,同時(shí)更新。
最后當(dāng)其中一個(gè)表（list2）所有值都賦值給新表后，在把另一個(gè)表的所有值直接尾插到新表就OK了，不管另一個(gè)表后有多少個(gè)值，都可以直接尾插并且完成鏈表的合并
之后返回我們記錄的tail就完成了（真是功夫不負(fù)有心人啊）文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-837210.html
注意要點(diǎn)：
- 初始創(chuàng)建表時(shí)，首節(jié)點(diǎn)為空，我們要讓它賦值原表的地址，應(yīng)該分類討論
- 注意各表的更新
- 當(dāng)其中一個(gè)表中所有的值都賦值完畢，另外一個(gè)表就可以全部尾插入新表中
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* list3=NULL;
struct ListNode* tail=NULL;
if(list1==NULL)
{
return list2; //若其中一個(gè)表為空則返回另一個(gè)表
}
if(list2==NULL)
{
return list1; //若其中一個(gè)表為空則返回另一個(gè)表
}
while(list1&&list2)
{
if(list1->val>list2->val) //返回小的值
{
if(list3==NULL)
{
tail=list3=list2; //如果新鏈表沒(méi)有頭則把較小值的地址賦值
}
else
{
list3->next = list2; //新鏈表的下一個(gè)節(jié)點(diǎn)指向較小值
list3=list3->next; //更新新鏈表
}
list2=list2->next; //更新已被賦值的較小值鏈表首地址
}
else if(list1->val<list2->val)
{
if(list3==NULL)
{
tail=list3=list1; //如果新鏈表沒(méi)有頭則把較小值的地址賦值
}
else
{
list3->next = list1;
list3=list3->next;
}
list1=list1->next;
}
else //兩值相同則賦值其中一個(gè)鏈表的首地址
{
if(list3==NULL)
{
tail=list3=list1; //如果新鏈表沒(méi)有頭則把較小值的地址賦值
}
else
{
list3->next = list1;
list3=list3->next;
}
list1=list1->next;
}
}
if(list1) //其中一個(gè)表全部賦值完畢，側(cè)再把另一個(gè)表的剩下值尾插到新表
{
list3->next=list1;
return tail;
}
else if(list2)
{
list3->next=list2;
return tail;
}
else
{
return tail;
}
}到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】鏈表OJ面試題(《刪除定值、反轉(zhuǎn)、返回中間結(jié)點(diǎn)、倒數(shù)第k節(jié)點(diǎn)、合并鏈表》）+解析)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
