目錄

鏈表分區（Partition）

功能概述

代碼實現

要點與難點

注意事項

鏈表回文判斷（PalindromeList）

功能概述

代碼實現

要點與難點

注意事項

總結

---

在鏈表相關的算法問題中，理解鏈表的基本結構和操作至關重要。今天我們深入探討兩個經典的鏈表問題：鏈表分區和鏈表回文判斷，通過詳細分析代碼實現，理解其中的要點、難點和注意事項。

作者主頁：共享家9527-CSDN博客

鏈表分區（Partition）

功能概述

鏈表分區的目標是將給定鏈表按照某個值?x?進行劃分，使得所有小于?x?的節點排在大于或等于?x?的節點之前。

代碼實現

?

cppclass Partition {public:ListNode* partition(ListNode* pHead, int x) {// 定義用于存儲大于等于x節點鏈表的頭指針和尾指針，以及小于x節點鏈表的頭指針和尾指針，還有遍歷原鏈表的指針struct ListNode* greatHead, *greattail, *lessHead, *lesstail, *cur;?// 為大于等于x節點鏈表的頭指針和尾指針分配內存，并初始化為同一節點greatHead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));?// 為小于x節點鏈表的頭指針和尾指針分配內存，并初始化為同一節點lessHead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));?// 將遍歷指針指向原鏈表頭節點cur = pHead;??// 遍歷原鏈表進行尾插while(cur){if(cur->val < x){// 將當前小于x的節點接到less鏈表的尾部lesstail->next = cur;??// 更新less鏈表的尾指針為當前節點lesstail = cur;? ?// 原鏈表中cur指針繼續指向下一個節點cur = cur->next;??}else{// 將當前大于等于x的節點接到great鏈表的尾部greattail->next = cur;?// 更新great鏈表的尾指針為當前節點greattail = cur;??// 原鏈表中cur指針繼續指向下一個節點cur = cur->next;??}}// 將less鏈表和great鏈表連接起來lesstail->next = greatHead->next;??// 將great鏈表的最后一個節點的next指針置為NULL，避免原鏈表的鏈接干擾greattail->next = NULL;? ? ? ? ? ?// 返回less鏈表的第一個有效節點（去掉虛擬頭節點）return lessHead->next;?}};

要點與難點

1.?虛擬頭節點的使用：為簡化鏈表操作，創建了兩個虛擬頭節點?lessHead?和?greatHead?，分別用于存儲小于?x?和大于等于?x?的節點。這避免了對鏈表頭節點的特殊處理，讓代碼更簡潔統一。

2.?尾插法：通過?lesstail?和?greattail?指針，采用尾插法將原鏈表中的節點分別插入到兩個新鏈表中，保持節點的相對順序。

3.?鏈表連接：遍歷結束后，將?lesstail?的?next?指針指向?greatHead->next?，實現兩個鏈表的連接。

4.?最后節點處理：必須將?greattail?的?next?指針設為?NULL?，否則可能會形成環或導致錯誤的鏈表結構。

注意事項

- 內存分配：使用?malloc?分配內存時，記得在不再使用時釋放內存，避免內存泄漏。

- 邊界條件：考慮鏈表為空或只有一個節點的情況，確保代碼的魯棒性。

鏈表回文判斷（PalindromeList）

功能概述

判斷給定的鏈表是否為回文鏈表，即正向和反向讀取鏈表節點的值是相同的。

代碼實現

?

cppclass PalindromeList {public:bool chkPalindrome(ListNode* A) {// 定義慢指針，初始指向鏈表頭節點struct ListNode* slow = A;?// 定義快指針，初始指向鏈表頭節點struct ListNode* fast = A;?// 利用快慢指針找鏈表中間節點，快指針每次走兩步，慢指針每次走一步while (fast->next) {?slow = slow->next;fast = fast->next;// 如果快指針還有下一個節點，再走一步if (fast->next) {?fast = fast->next;}}// 用于存儲反轉后半部分鏈表的新頭指針struct ListNode* change = NULL;?// 從中間節點開始處理后半部分鏈表struct ListNode* head = slow;?// 反轉鏈表的后半部分while (head) {// 保存當前節點的下一個節點struct ListNode* next = head->next;?// 將當前節點指向前一個節點，實現反轉head->next = change;?// 更新新的頭指針為當前節點change = head;?// 繼續處理下一個節點head = next;?}// 比較鏈表的前半部分和反轉后的后半部分while (slow) {// 如果對應節點值不相等，返回falseif (A->val != change->val) {?return false;}// 前半部分鏈表指針后移A = A->next;?// 反轉后的后半部分鏈表指針后移change = change->next;?}// 所有對應節點值都相等，返回truereturn true;?}};

要點與難點

1.?快慢指針：利用快慢指針找到鏈表的中間節點。快指針每次移動兩步，慢指針每次移動一步，當快指針到達鏈表末尾時，慢指針正好指向中間節點。這是找到鏈表中間位置的高效方法。

2.?鏈表反轉：將鏈表的后半部分進行反轉，通過改變指針方向實現。在反轉過程中，需要小心處理指針的指向，確保鏈表結構不被破壞。

3.?比較判斷：從鏈表的兩端開始比較節點的值，若所有值都相同，則鏈表為回文鏈表。

注意事項

- 指針操作：在鏈表反轉過程中，要注意保存當前節點的下一個節點，以免丟失鏈表結構。

- 邊界條件：考慮鏈表長度為奇數和偶數的情況，確保代碼在各種情況下都能正確判斷。比如鏈表長度為奇數時，中間節點單獨處理，不參與比較；鏈表長度為偶數時，中間兩個節點分別屬于前后兩部分參與比較 。

總結

鏈表操作需要對指針有深入的理解和熟練的運用。無論是鏈表分區還是回文判斷，關鍵在于合理利用指針來遍歷、修改鏈表結構。在實現過程中，要注意邊界條件的處理、內存管理以及代碼的可讀性和可維護性。通過不斷練習和總結，我們可以更好地掌握鏈表相關的算法問題，提高編程能力。