链表的回文结构（画图精讲）

本文主要是介绍链表的回文结构（画图精讲），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目的讲解

解决思路

1，先找中间节点

2，然会进行逆置

3，最后进行对比

 1，找到中间节点

这个我们采取快慢指针，来找到中间节点

快慢指针是一种常用的技巧，用于在链表或数组中找到中间节点、检测循环或者解决其他问题。快慢指针通常包括两个指针，一个快指针和一个慢指针。快指针每次移动两个节点，而慢指针每次移动一个节点。当快指针到达链表的末尾时，慢指针将指向链表的中间节点。
下面是快慢指针在链表中找到中间节点的步骤：
1. 初始化两个指针，快指针（fast）和慢指针（slow），都指向链表的头节点。
2. 在每次迭代中，将快指针向前移动两个节点，将慢指针向前移动一个节点。
3. 当快指针到达链表的末尾（即快指针为NULL或者快指针的下一个节点为NULL）时，慢指针将指向链表的中间节点。
如果链表的长度是奇数，慢指针将指向中间的节点；如果链表的长度是偶数，慢指针将指向中间两个节点的第一个节点。
下面是一个使用快慢指针在链表中找到中间节点的示例代码：

```c
ListNode* FindMid(ListNode* head) {if (head == NULL || head->next == NULL) {return head; // 链表为空或只有一个节点时，中间节点就是头节点}ListNode* slow = head;ListNode* fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;       // 慢指针前进一步fast = fast->next->next; // 快指针前进两步}return slow; // 慢指针指向中间节点
}
```

在这个示例中，当快指针到达链表的末尾时，慢指针将指向链表的中间节点。如果链表有偶数个节点，慢指针将指向第二个中间节点。如果需要找到第一个中间节点，可以在循环结束后将慢指针再向前移动一个节点。

这里的判断条件看清楚，都是对快指针的判断，因为快慢指针涉及的是奇偶数

 while (fast != NULL && fast->next != NULL) 

2，然会进行逆置

逆置这里，不能直接进行逆置，直接进行逆置的情况下，容易导致循环节点，所以需要修改一下，也就是创建一个指针指向头结点

单链表逆置（这里还是有点难度的）

也称为链表翻转，是将链表中的元素顺序颠倒的过程。在单链表中，每个节点都有一个指向下一个节点的指针。逆置链表意味着改变每个节点的指向，使其指向前一个节点，而不是下一个节点。
链表逆置的常用方法是使用头插法。头插法是一种常用的链表操作技巧，用于在链表的头部插入新节点。在链表逆置过程中，我们可以从头开始遍历原始链表，并将每个节点作为新链表的头节点插入。
以下是单链表逆置的步骤：
1. 初始化两个指针，一个指向原始链表的头节点（current），另一个指向新链表的头部（newHead），初始时新链表为空。
2. 遍历原始链表：
   a. 使用临时指针（next）保存当前节点的下一个节点。
   b. 将当前节点的下一个节点指向新链表的头部（newHead），实现头插法。
   c. 更新新链表的头部为当前节点。
   d. 将当前节点移动到下一个节点（即临时指针指向的节点）。
3. 当原始链表遍历完毕后，新链表即为逆置后的链表。
下面是一个使用头插法逆置单链表的示例代码：

ListNode* Reverse(ListNode* head) {ListNode* newHead = NULL; // 新链表的头部ListNode* current = head; // 当前遍历的节点while (current != NULL) {ListNode* next = current->next; // 保存下一个节点current->next = newHead; // 将当前节点的下一个节点指向新链表的头部newHead = current; // 更新新链表的头部为当前节点current = next; // 移动当前节点到下一个节点}return newHead; // 返回新链表的头部
}

在这个示例中，`Reverse` 函数接受一个链表的头节点 `head` 作为参数，并返回逆置后的链表的头节点 `newHead`。通过头插法，原始链表中的每个节点都被逆序插入到新链表的头部，从而实现了链表的逆置。
 

图解

1，首先这里是一个环回链表，我们已经找到了中间节点

2，此时我们设置好变量

3，我们进行逆置的行动

我们不能直接进行逆置，这样的话会导致最后进行对比的时候，产生循环所以我们需要让中间数值的下一个节点指向null，然后再进行下面节点的转化

 3，最后进行对比

也就是，

代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
//进行重命名
#include <cstddef>
class PalindromeList {
public:
typedef struct ListNode ListNode;
//找到中间节点
ListNode* FindMid(ListNode* head)
{if(head == NULL || head->next == NULL){return head;}ListNode*slow =head;ListNode*fast =head;//这里的判断判断全部都是奇偶数while(fast && fast->next){slow=slow->next;fast=fast->next->next;}//返回中间节点return slow;
}//翻转链表
ListNode* Flip(ListNode* mid)
{ListNode* newhead = NULL;ListNode* cur = mid;while (cur) {ListNode* next= cur->next;//进行头插，不能直接进行链表的翻转，不然会产生回环链表cur->next = newhead;newhead = cur;cur = next;}return newhead;
}//进行对比，是回文结构就进行返回bool数值，不是的话返回null
bool chkPalindrome(ListNode* A)
{ListNode*mid= FindMid(A);ListNode*title=Flip(mid);while(A && title){if(A->val != title->val){return false;}A = A->next;title = title->next;}return true;
}};

 

这篇关于链表的回文结构（画图精讲）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---