溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇“C語言怎么移除鏈表元素”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C語言怎么移除鏈表元素”文章吧。
鏈接直達：
移除鏈表元素
題目：
思路：
此題要綜合考慮多種情況，常規情況就如同示例1，有多個節點，并且val不連續，但是非常規呢？當val連續呢？當頭部就是val呢？所以要分類討論
常規情況：
需要定義兩個指針prev和cur，cur指向第一個數據，prev指向cur的前一個。依次遍歷cur指向的數據是否為val，若是，則把prev的下一個節點指向cur的下一個節點上，cur=cur->next，prev跟著cur一起走，直到cur走到NULL
連續val：
當我們仔細觀察下，不難發現，在常規情況下是可以解決連續val的，但是頭部val就不可了
頭部val：
此時除了剛才定義的兩個指針prev和cur外，還要有個head指向頭部，當頭部是val時，將cur指向下一個位置，head跟著一起動，直到cur指向的數據不為val時，將head賦給prev。此時剩余的就按常規處理即可。
代碼如下：
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;
}鏈接直達：
反轉鏈表
題目：
思路：
法一：三指針翻轉方向
定義三個指針n1，n2，n3分別用來指向NULL，第一個數據，第二個數據。讓n2的next指向n1，把n2賦給n1，再把n3賦給n2，再執行n3=n3->next的操作，接下來重復上述操作，直到n2指向空即可。但是要注意，要先判斷該鏈表是否為NULL，如果是，則返回NULL，此外，還要保證當n3為空時就不要動了，直接把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;
}法二：頭插
此法就需要再創建一個鏈表了，創建一個新的頭部newhead指向NULL，再定義一個指針cur指向原鏈表第一個數據，注意還得定義一個指針next指向cur的下一個節點。遍歷原鏈表，把節點取下來頭插到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;
}鏈接直達：
鏈表的中間節點
題目：
思路：
快慢指針
這道題要注意奇偶數，如果為奇數，如示例1，那么中間節點值就是3，反之偶數如示例2，返回第二個中間節點。此題我們定義兩個指針slow和fast都指向第一個數據的位置，區別在于讓slow一次走1步，fast一次走2步。當fast走到尾指針時，slow就是中間節點
代碼如下：
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;
}鏈接直達：
鏈表中倒數第k個節點
題目：
思路：
快慢指針
定義兩個指針slow和fast，讓fast先走k步，再讓slow和fast同時走，當fast走到尾部時，slow就是倒數第k個，因為這樣的話slow和fast的差距始終是k個，當fast走到空時結束。此題同樣可以走k-1步，不過當fast走到尾部時結束，也就是fast的下一個節點指向空時結束，都一樣。先拿走k步舉例，如圖所示：
代碼如下：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
struct ListNode*fast=pListHead;
struct ListNode*slow=pListHead;
while(k--)
{
//if判斷，防止k大于鏈表的長度
if(fast==NULL)
return NULL;
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}鏈接直達：
合并兩個有序鏈表
題目：
思路：
法一：歸并（取小的尾插）--- 帶頭節點
假設新鏈表的頭叫head并指向NULL，還需要定義一個指針tail來方便后續的找尾，依次比較list1和list2節點的值，把小的放到新鏈表head上，并更新tail，再把list1或list2更新一下。當list1和list2兩個鏈表中一個走到空時，直接把剩下的鏈表所有剩下的元素拷進去即可
代碼如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//檢查list1或list2一開始就為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;
}
}
//當list1和list2其中一個走到空的情況
if(list1==NULL)
{
tail->next=list2;
}
else
{
tail->next=list1;
}
return head;
}法二：哨兵位的頭節點
解釋下帶頭節點：
比如說同樣一個鏈表存1，2，3。不帶頭節點只有這三個節點，head指向1。而帶頭節點的同樣存3個值，不過有4個節點，head指向頭部這個節點，這個節點不存儲有效數據
帶頭結點有如下好處，不用判斷head和tail是否為空了，也不用判斷list1和list2是否為空了，會方便不少。和上述思路一樣，取小的下來尾插，直接鏈接到tail后面即可。但是要注意返回的時候要返回head的next，因為題目給的鏈表是不帶頭的，而head本身指向的就是那個頭，所以要返回下一個。
代碼如下：
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;
}
}
//當list1和list2其中一個走到空的情況
if (list1 == NULL)
{
tail->next = list2;
}
else
{
tail->next = list1;
}
struct ListNode* list = head->next;
free(head);
head = NULL
return list;
}鏈接直達：
鏈表分割
題目：
思路：
定義兩個鏈表lesshead和greaterhead。遍歷原鏈表，把 < x 的插入到鏈表1，把 > x 的插入到鏈表2，最后再把鏈表1和鏈表2鏈接起來。在定義兩個尾指針以跟進鏈表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;
}
};以上就是關于“C語言怎么移除鏈表元素”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
