LeetCodeOJ题:回文链表

题目链接

回文链表

题目描述

 

解题思路：

 1.找到链表中间节点：

使用快慢指针法。定义两个指针，慢指针每次移动一个节点，快指针每次移动两个节点。当快指针到达链表末尾时，慢指针就会指向链表的中间节点。如果链表有奇数个节点，慢指针指向正中间的节点；如果链表有偶数个节点，慢指针指向正中间右边的节点。例如对于链表1->2->3->4->5，慢指针最终会指向3；对于链表1->2->3->4，慢指针会指向3。

2.反转后半部分链表：

从中间节点开始，将其后的链表进行反转。可以使用迭代或递归的方式实现链表反转。反转后，原链表后半部分的顺序被颠倒，这样就可以方便地与前半部分进行比较。例如，对于链表1->2->3->4->5，找到中点3后，将3之后的4->5反转成5->4，得到两条链表1->2->3和5->4。 

 

3.比较前后两部分链表：

设置两个指针，一个从原链表的头节点开始，另一个从反转后的后半部分链表的头节点开始，同时遍历这两条链表，每次循环比较两个指针所指向节点的值是否相等。如果不相等，则说明链表不是回文链表，返回false。如果循环直到反转后的后半部分链表遍历结束，都没有出现不相等的情况，说明链表是回文链表，返回true。 

整体过程如下

  

疑难疑点 

• 关于不反转整个链表的原因：如果反转整个链表，确实可以从新的头节点开始依次访问原链表的最后一个节点、倒数第二个节点等，但这样会破坏链表前半段的结构。而我们需要同时遍历原链表的前半部分和后半部分来进行比较，若反转整个链表，就无法正常获取原链表前半部分的节点顺序，导致无法实现通过比较前后部分来判断回文的逻辑7。

 完整代码：