链表利用：分区与回文判断

目次
链表分区（Partition）
功能概述
代码实现
要点与难点
注意事项
链表回文判断（PalindromeList）
功能概述
代码实现
要点与难点
注意事项
总结

---

   在链表干系的算法标题中，明确链表的根本布局和利用至关告急。本日我们深入探究两个经典的链表标题：链表分区和链表回文判断，通过具体分析代码实现，明确此中的要点、难点和注意事项。
  

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



链表分区（Partition）


功能概述


链表分区的目标是将给定链表按照某个值 x 举行分别，使得全部小于 x 的节点排在大于或便是 x 的节点之前。

代码实现


 

1. cpp
3. class Partition {
5. public:
7.     ListNode* partition(ListNode* pHead, int x) {
9.         // 定义用于存储大于等于x节点链表的头指针和尾指针，以及小于x节点链表的头指针和尾指针，还有遍历原链表的指针
11.         struct ListNode* greatHead, *greattail, *lessHead, *lesstail, *cur; 
13.         // 为大于等于x节点链表的头指针和尾指针分配内存，并初始化为同一节点
15.         greatHead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode)); 
17.         // 为小于x节点链表的头指针和尾指针分配内存，并初始化为同一节点
19.         lessHead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode)); 
21.         // 将遍历指针指向原链表头节点
23.         cur = pHead;  
27.         // 遍历原链表进行尾插
29.         while(cur)
31.         {
33.             if(cur->val < x)
35.             {
37.                 // 将当前小于x的节点接到less链表的尾部
39.                 lesstail->next = cur;  
41.                 // 更新less链表的尾指针为当前节点
43.                 lesstail = cur;   
45.                 // 原链表中cur指针继续指向下一个节点
47.                 cur = cur->next;  
49.             }
51.             else
53.             {
55.                 // 将当前大于等于x的节点接到great链表的尾部
57.                 greattail->next = cur; 
59.                 // 更新great链表的尾指针为当前节点
61.                 greattail = cur;  
63.                 // 原链表中cur指针继续指向下一个节点
65.                 cur = cur->next;  
67.             }
69.         }
73.         // 将less链表和great链表连接起来
75.         lesstail->next = greatHead->next;  
77.         // 将great链表的最后一个节点的next指针置为NULL，避免原链表的链接干扰
79.         greattail->next = NULL;           
83.         // 返回less链表的第一个有效节点（去掉虚拟头节点）
85.         return lessHead->next; 
87.     }
89. };

复制代码

要点与难点

   
  1. 捏造头节点的使用：为简化链表利用，创建了两个捏造头节点 lessHead 和 greatHead ，分别用于存储小于 x 和大于便是 x 的节点。这制止了对链表头节点的特殊处理处罚，让代码更简便同一。
  
  2. 尾插法：通过 lesstail 和 greattail 指针，采取尾插法将原链表中的节点分别插入到两个新链表中，保持节点的相对次序。
  
  3. 链表毗连：遍历竣事后，将 lesstail 的 next 指针指向 greatHead->next ，实现两个链表的毗连。
  
  4. 末了节点处理处罚：必须将 greattail 的 next 指针设为 NULL ，否则大概会形成环或导致错误的链表布局。
  
注意事项

   
  - 内存分配：使用 malloc 分配内存时，记得在不再使用时开释内存，制止内存走漏。
  
  - 边界条件：思量链表为空或只有一个节点的环境，确保代码的鲁棒性。
  
链表回文判断（PalindromeList）


功能概述


判断给定的链表是否为回文链表，即正向和反向读取链表节点的值是雷同的。

代码实现


 

1. cpp
3. class PalindromeList {
5.   public:
7.     bool chkPalindrome(ListNode* A) {
9.         // 定义慢指针，初始指向链表头节点
11.         struct ListNode* slow = A; 
13.         // 定义快指针，初始指向链表头节点
15.         struct ListNode* fast = A; 
17.         // 利用快慢指针找链表中间节点，快指针每次走两步，慢指针每次走一步
19.         while (fast->next) { 
21.             slow = slow->next;
23.             fast = fast->next;
25.             // 如果快指针还有下一个节点，再走一步
27.             if (fast->next) { 
29.                 fast = fast->next;
31.             }
33.         }
35.         // 用于存储反转后半部分链表的新头指针
37.         struct ListNode* change = NULL; 
39.         // 从中间节点开始处理后半部分链表
41.         struct ListNode* head = slow; 
43.         // 反转链表的后半部分
45.         while (head) {
47.             // 保存当前节点的下一个节点
49.             struct ListNode* next = head->next; 
51.             // 将当前节点指向前一个节点，实现反转
53.             head->next = change; 
55.             // 更新新的头指针为当前节点
57.             change = head; 
59.             // 继续处理下一个节点
61.             head = next; 
63.         }
65.         // 比较链表的前半部分和反转后的后半部分
67.         while (slow) {
69.             // 如果对应节点值不相等，返回false
71.             if (A->val != change->val) { 
73.                 return false;
75.             }
77.             // 前半部分链表指针后移
79.             A = A->next; 
81.             // 反转后的后半部分链表指针后移
83.             change = change->next; 
85.         }
87.         // 所有对应节点值都相等，返回true
89.         return true; 
91.     }
93. };

复制代码

要点与难点

   
  1. 快慢指针：使用快慢指针找到链表的中心节点。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表末了时，慢指针恰恰指向中心节点。这是找到链表中心位置的高效方法。
  
  2. 链表反转：将链表的后半部分举行反转，通过改变指针方向实现。在反转过程中，必要鉴戒处理处罚指针的指向，确保链表布局不被粉碎。
  
  3. 比力判断：从链表的两头开始比力节点的值，若全部值都雷同，则链表为回文链表。
  
注意事项

   
  - 指针利用：在链表反转过程中，要注意生存当前节点的下一个节点，以免丢失链表布局。
  
  - 边界条件：思量链表长度为奇数和偶数的环境，确保代码在各种环境下都能精确判断。好比链表长度为奇数时，中心节点单独处理处罚，不到场比力；链表长度为偶数时，中心两个节点分别属于前后两部分到场比力 。
  

总结


   链表利用必要对指针有深入的明确和纯熟的运用。无论是链表分区照旧回文判断，关键在于公道使用指针来遍历、修改链表布局。在实现过程中，要注意边界条件的处理处罚、内存管理以及代码的可读性和可维护性。通过不绝练习和总结，我们可以更好地把握链表干系的算法标题，进步编程本领。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。