鏈表作為一種基礎的數(shù)據(jù)結構，在程序設計中扮演著重要角色。掌握鏈表的高效操作技巧，特別是逆序、合并和循環(huán)檢測，對于提升算法性能和解決復雜問題至關重要。本文將詳細介紹這些操作的C語言實現(xiàn)，并分析其時間復雜度。
鏈表節(jié)點定義
首先，我們定義鏈表節(jié)點的結構：
c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
鏈表逆序的高效實現(xiàn)
鏈表逆序是一個經(jīng)典問題，可以通過迭代或遞歸方式實現(xiàn)。這里介紹一種高效的迭代方法，時間復雜度為O(n)，空間復雜度為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é)點。
遍歷鏈表，保存當前節(jié)點的下一個節(jié)點nextTemp。
將當前節(jié)點的next指針指向prev，實現(xiàn)局部逆序。
移動prev和curr指針，繼續(xù)處理下一個節(jié)點。
最終prev成為新鏈表的頭節(jié)點。
鏈表合并的高效實現(xiàn)
合并兩個有序鏈表也是一個常見問題。這里實現(xiàn)一個時間復雜度為O(n+m)的高效算法，其中n和m分別是兩個鏈表的長度。
c
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0); // 啞節(jié)點簡化操作
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é)點
tail->next = (l1 != NULL) ? l1 : l2;
return dummy.next;
}
代碼解析
使用啞節(jié)點dummy簡化頭節(jié)點處理。
比較兩個鏈表當前節(jié)點的值，將較小者連接到結果鏈表。
移動相應鏈表的指針和結果鏈表的尾指針。
當任一鏈表遍歷完后，將另一鏈表的剩余部分直接連接。
鏈表循環(huán)檢測的高效實現(xiàn)
檢測鏈表中是否存在環(huán)是一個重要問題。這里使用Floyd判圈算法（龜兔賽跑算法），時間復雜度為O(n)，空間復雜度為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，快指針初始位置比慢指針前進一步。
慢指針每次移動一步，快指針每次移動兩步。
如果存在環(huán)，快慢指針最終會相遇；如果不存在環(huán)，快指針會先到達鏈表尾部。
完整示例與測試
c
// 創(chuàng)建鏈表節(jié)點
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() {
// 測試鏈表逆序
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);
// 測試鏈表合并
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);
// 測試循環(huán)檢測
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)存，適合處理長鏈表。
合并操作：使用啞節(jié)點可以避免處理空鏈表的特殊情況，使代碼更簡潔。
循環(huán)檢測：Floyd算法是最優(yōu)解，但要注意指針初始化的差異（本例中快指針初始前進一步是為了檢測相鄰節(jié)點成環(huán)的情況）。
這些高效技巧不僅適用于基本鏈表操作，還可以擴展到更復雜的數(shù)據(jù)結構問題中。理解其原理和實現(xiàn)細節(jié)，對于提升編程能力和解決實際問題具有重要意義。
下載文檔
