www.久久久久|狼友网站av天堂|精品国产无码a片|一级av色欲av|91在线播放视频|亚洲无码主播在线|国产精品草久在线|明星AV网站在线|污污内射久久一区|婷婷综合视频网站

當(dāng)前位置:首頁(yè) > 嵌入式 > 嵌入式分享
[導(dǎo)讀]鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),在程序設(shè)計(jì)中扮演著重要角色。掌握鏈表的高效操作技巧,特別是逆序、合并和循環(huán)檢測(cè),對(duì)于提升算法性能和解決復(fù)雜問(wèn)題至關(guān)重要。本文將詳細(xì)介紹這些操作的C語(yǔ)言實(shí)現(xiàn),并分析其時(shí)間復(fù)雜度。


鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),在程序設(shè)計(jì)中扮演著重要角色。掌握鏈表的高效操作技巧,特別是逆序、合并和循環(huán)檢測(cè),對(duì)于提升算法性能和解決復(fù)雜問(wèn)題至關(guān)重要。本文將詳細(xì)介紹這些操作的C語(yǔ)言實(shí)現(xiàn),并分析其時(shí)間復(fù)雜度。


鏈表節(jié)點(diǎn)定義

首先,我們定義鏈表節(jié)點(diǎn)的結(jié)構(gòu):


c

#include <stdio.h>

#include <stdlib.h>


typedef struct ListNode {

   int val;

   struct ListNode *next;

} ListNode;

鏈表逆序的高效實(shí)現(xiàn)

鏈表逆序是一個(gè)經(jīng)典問(wèn)題,可以通過(guò)迭代或遞歸方式實(shí)現(xiàn)。這里介紹一種高效的迭代方法,時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。


c

ListNode* reverseList(ListNode* head) {

   ListNode *prev = NULL;

   ListNode *curr = head;

   while (curr != NULL) {

       ListNode *nextTemp = curr->next;

       curr->next = prev;

       prev = curr;

       curr = nextTemp;

   }

   return prev;

}

代碼解析

初始化prev為NULL,curr指向頭節(jié)點(diǎn)。

遍歷鏈表,保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)nextTemp。

將當(dāng)前節(jié)點(diǎn)的next指針指向prev,實(shí)現(xiàn)局部逆序。

移動(dòng)prev和curr指針,繼續(xù)處理下一個(gè)節(jié)點(diǎn)。

最終prev成為新鏈表的頭節(jié)點(diǎn)。

鏈表合并的高效實(shí)現(xiàn)

合并兩個(gè)有序鏈表也是一個(gè)常見問(wèn)題。這里實(shí)現(xiàn)一個(gè)時(shí)間復(fù)雜度為O(n+m)的高效算法,其中n和m分別是兩個(gè)鏈表的長(zhǎng)度。


c

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

   ListNode dummy(0); // 啞節(jié)點(diǎn)簡(jiǎn)化操作

   ListNode *tail = &dummy;

   

   while (l1 != NULL && l2 != NULL) {

       if (l1->val <= l2->val) {

           tail->next = l1;

           l1 = l1->next;

       } else {

           tail->next = l2;

           l2 = l2->next;

       }

       tail = tail->next;

   }

   

   // 處理剩余節(jié)點(diǎn)

   tail->next = (l1 != NULL) ? l1 : l2;

   return dummy.next;

}

代碼解析

使用啞節(jié)點(diǎn)dummy簡(jiǎn)化頭節(jié)點(diǎn)處理。

比較兩個(gè)鏈表當(dāng)前節(jié)點(diǎn)的值,將較小者連接到結(jié)果鏈表。

移動(dòng)相應(yīng)鏈表的指針和結(jié)果鏈表的尾指針。

當(dāng)任一鏈表遍歷完后,將另一鏈表的剩余部分直接連接。

鏈表循環(huán)檢測(cè)的高效實(shí)現(xiàn)

檢測(cè)鏈表中是否存在環(huán)是一個(gè)重要問(wèn)題。這里使用Floyd判圈算法(龜兔賽跑算法),時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。


c

int hasCycle(ListNode *head) {

   if (head == NULL || head->next == NULL) {

       return 0;

   }

   

   ListNode *slow = head;

   ListNode *fast = head->next;

   

   while (slow != fast) {

       if (fast == NULL || fast->next == NULL) {

           return 0;

       }

       slow = slow->next;

       fast = fast->next->next;

   }

   

   return 1;

}

代碼解析

初始化慢指針slow和快指針fast,快指針初始位置比慢指針前進(jìn)一步。

慢指針每次移動(dòng)一步,快指針每次移動(dòng)兩步。

如果存在環(huán),快慢指針最終會(huì)相遇;如果不存在環(huán),快指針會(huì)先到達(dá)鏈表尾部。

完整示例與測(cè)試

c

// 創(chuàng)建鏈表節(jié)點(diǎn)

ListNode* createNode(int val) {

   ListNode* node = (ListNode*)malloc(sizeof(ListNode));

   node->val = val;

   node->next = NULL;

   return node;

}


// 打印鏈表

void printList(ListNode* head) {

   while (head != NULL) {

       printf("%d ", head->val);

       head = head->next;

   }

   printf("\n");

}


int main() {

   // 測(cè)試鏈表逆序

   ListNode *head = createNode(1);

   head->next = createNode(2);

   head->next->next = createNode(3);

   printf("Original list: ");

   printList(head);

   head = reverseList(head);

   printf("Reversed list: ");

   printList(head);

   

   // 測(cè)試鏈表合并

   ListNode *l1 = createNode(1);

   l1->next = createNode(3);

   ListNode *l2 = createNode(2);

   l2->next = createNode(4);

   ListNode *merged = mergeTwoLists(l1, l2);

   printf("Merged list: ");

   printList(merged);

   

   // 測(cè)試循環(huán)檢測(cè)

   ListNode *cycleHead = createNode(1);

   cycleHead->next = createNode(2);

   cycleHead->next->next = createNode(3);

   cycleHead->next->next->next = cycleHead->next; // 創(chuàng)建環(huán)

   printf("List has cycle: %d\n", hasCycle(cycleHead));

   

   return 0;

}

性能分析與優(yōu)化建議

逆序操作:迭代方法比遞歸方法更節(jié)省內(nèi)存,適合處理長(zhǎng)鏈表。

合并操作:使用啞節(jié)點(diǎn)可以避免處理空鏈表的特殊情況,使代碼更簡(jiǎn)潔。

循環(huán)檢測(cè):Floyd算法是最優(yōu)解,但要注意指針初始化的差異(本例中快指針初始前進(jìn)一步是為了檢測(cè)相鄰節(jié)點(diǎn)成環(huán)的情況)。

這些高效技巧不僅適用于基本鏈表操作,還可以擴(kuò)展到更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)問(wèn)題中。理解其原理和實(shí)現(xiàn)細(xì)節(jié),對(duì)于提升編程能力和解決實(shí)際問(wèn)題具有重要意義。

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國(guó)汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來(lái)越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來(lái)越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽(yáng)舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語(yǔ)權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國(guó)電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉