鏈表操作的高效技巧：逆序、合并與循環(huán)檢測(cè)的C語(yǔ)言實(shí)現(xiàn)
鏈表作為一種基礎(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è)常見(jiàn)問(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)題具有重要意義。
下載文檔
