回文链表（ LeetCode 234 ）
一、题目描述
请判断一个链表是否为回文链表。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 回文链表（ LeetCode 234 ）: https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution {
public boolean isPalindrome(ListNode head) {
// 边界情况判断
// 链表为空或者只有一个节点的情况，属于回文链表
if(head == null || head.next == null) return true;
// 链表只有两个节点的时候，判断这两个节点值是否相等
if(head.next.next == null) return head.val == head.next.val;
// 通过快慢指针寻找链表的中心点
// 设置一个指针，指向链表的头部
// fast 这个指针每次都向后移动两步
ListNode fast = head;
// 设置一个指针，指向链表的头部
// slow 这个指针每次都向后移动一步
ListNode slow = head;
// 让 fast 和 slow 同时向后移动
// 其中，fast 这个指针每次都向后移动两步，slow 这个指针每次都向后移动一步
// 直到 fast 这个指针指向了链表的尾节点，即 fast.next = null
// 或者 fast 这个指针指向了链表的尾节点的前一个节点，即 fast.next.next = null
// 这个时候，fast 这个指针无法向后移动两位，跳出循环，找到了中间点
// 如果链表长度为偶数，则 slow 指向了中间节点前的那个节点
// 比如链表为 1 --> 2 --> 3 --> 4 --> null
// 一开始，slow 和 fast 同时指向 1，slow 移动一位到 2，fast 移动两位到 3
// 由于 3.next.next 为空，所以跳出 while，此时 slow 指向了中间节点前的那个节点
// 如果链表长度为奇数，则 slow 指向了中间节点
// 比如链表为 1 --> 2 --> 3
// 一开始，slow 和 fast 同时指向 1，slow 移动一位到 2，fast 移动两位到 3
// 由于 3.next 为空，所以跳出 while，此时 slow 指向了中间节点
while(fast.next != null && fast.next.next != null){
// slow 这个指针每次都向后移动一步
slow = slow.next;
// fast 这个指针每次都向后移动两步
fast = fast.next.next;
}
// 这个时候，slow 指向的那个节点把链表划分为两个区域
// 翻转右区域的链表
// 获取右区域的链表翻转之后的头节点
ListNode rightHead = reverse(slow.next);
// 获取左区域的链表的头节点
ListNode leftHead = head;
// 让 leftHead 和 rightHead 同时向后移动，直到 rightHead 指向 null 为止
// 说明比较完了所有的节点
while(rightHead != null){
// 如果它们的节点值不一样，那么就不是回文链表
if(leftHead.val != rightHead.val){
// 不是回文链表，返回 false
return false;
}
// 否则，让 rightHead 继续向右移动
rightHead = rightHead.next;
// 否则，让 rightHead 继续向右移动
leftHead = leftHead.next;
}
// 比较完所有的节点，说明是回文链表，返回 true
return true;
}
// 反转链表的代码
private ListNode reverse(ListNode head) {
// 寻找递归终止条件
// 1、head 指向的结点为 null
// 2、head 指向的结点的下一个结点为 null
// 在这两种情况下，反转之后的结果还是它自己本身
if( head == null || head.next == null) return head;
// 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
// 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
ListNode cur = reverse(head.next);
// 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
// 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
// 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
// 等号右侧为 head，意思就是设置 5 的下一个节点是 4
// 这里出现了两个 next
// 第一个 next 是「获取」 head 的下一节点
// 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
head.next.next = head;
// head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
// 否则会发生无限循环
head.next = null;
// 我们把每次反转后的结果传递给上一层
return cur;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 回文链表（ LeetCode 234 ）: https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution {
public:
bool isPalindrome(ListNode* head) {
// 边界情况判断
// 链表为空或者只有一个节点的情况，属于回文链表
if(head == NULL || head->next == NULL) return true;
// 链表只有两个节点的时候，判断这两个节点值是否相等
if(head->next->next == NULL) return head->val == head->next->val;
// 通过快慢指针寻找链表的中心点
// 设置一个指针，指向链表的头部
// fast 这个指针每次都向后移动两步
ListNode* fast = head;
// 设置一个指针，指向链表的头部
// slow 这个指针每次都向后移动一步
ListNode* slow = head;
// 让 fast 和 slow 同时向后移动
// 其中，fast 这个指针每次都向后移动两步，slow 这个指针每次都向后移动一步
// 直到 fast 这个指针指向了链表的尾节点，即 fast->next = NULL
// 或者 fast 这个指针指向了链表的尾节点的前一个节点，即 fast->next->next = NULL
// 这个时候，fast 这个指针无法向后移动两位，跳出循环，找到了中间点
// 如果链表长度为偶数，则 slow 指向了中间节点前的那个节点
// 比如链表为 1 --> 2 --> 3 --> 4 --> NULL
// 一开始，slow 和 fast 同时指向 1，slow 移动一位到 2，fast 移动两位到 3
// 由于 3->next->next 为空，所以跳出 while，此时 slow 指向了中间节点前的那个节点
// 如果链表长度为奇数，则 slow 指向了中间节点
// 比如链表为 1 --> 2 --> 3
// 一开始，slow 和 fast 同时指向 1，slow 移动一位到 2，fast 移动两位到 3
// 由于 3->next 为空，所以跳出 while，此时 slow 指向了中间节点
while(fast->next != NULL && fast->next->next != NULL){
// slow 这个指针每次都向后移动一步
slow = slow->next;
// fast 这个指针每次都向后移动两步
fast = fast->next->next;
}
// 这个时候，slow 指向的那个节点把链表划分为两个区域
// 翻转右区域的链表
// 获取右区域的链表翻转之后的头节点
ListNode* rightHead = reverse(slow->next);
// 获取左区域的链表的头节点
ListNode* leftHead = head;
// 让 leftHead 和 rightHead 同时向后移动，直到 rightHead 指向 NULL 为止
// 说明比较完了所有的节点
while(rightHead != NULL){
// 如果它们的节点值不一样，那么就不是回文链表
if(leftHead->val != rightHead->val){
// 不是回文链表，返回 false
return false;
}
// 否则，让 rightHead 继续向右移动
rightHead = rightHead->next;
// 否则，让 rightHead 继续向右移动
leftHead = leftHead->next;
}
// 比较完所有的节点，说明是回文链表，返回 true
return true;
}
// 反转链表的代码
private:
ListNode* reverse(ListNode* head) {
// 寻找递归终止条件
// 1、head 指向的结点为 NULL
// 2、head 指向的结点的下一个结点为 NULL
// 在这两种情况下，反转之后的结果还是它自己本身
if( head == NULL || head->next == NULL) return head;
// 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
// 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
ListNode* cur = reverse(head->next);
// 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
// 第一次执行下面代码的时候，head 为 4，那么 head->next = 5
// 那么 head->next->next 就是 5->next ，意思就是去设置 5 的下一个节点
// 等号右侧为 head，意思就是设置 5 的下一个节点是 4
// 这里出现了两个 next
// 第一个 next 是「获取」 head 的下一节点
// 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
head->next->next = head;
// head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
// 否则会发生无限循环
head->next = NULL;
// 我们把每次反转后的结果传递给上一层
return cur;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 回文链表（ LeetCode 234 ）: https://leetcode-cn.com/problems/palindrome-linked-list/
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
# 边界情况判断
# 链表为空或者只有一个节点的情况，属于回文链表
if head == None or head.next == None :
return True
# 链表只有两个节点的时候，判断这两个节点值是否相等
if head.next.next == None :
return head.val == head.next.val
# 通过快慢指针寻找链表的中心点
# 设置一个指针，指向链表的头部
# fast 这个指针每次都向后移动两步
fast = head
# 设置一个指针，指向链表的头部
# slow 这个指针每次都向后移动一步
slow = head
# 让 fast 和 slow 同时向后移动
# 其中，fast 这个指针每次都向后移动两步，slow 这个指针每次都向后移动一步
# 直到 fast 这个指针指向了链表的尾节点，即 fast.next = None
# 或者 fast 这个指针指向了链表的尾节点的前一个节点，即 fast.next.next = None
# 这个时候，fast 这个指针无法向后移动两位，跳出循环，找到了中间点
# 如果链表长度为偶数，则 slow 指向了中间节点前的那个节点
# 比如链表为 1 --> 2 --> 3 --> 4 --> None
# 一开始，slow 和 fast 同时指向 1，slow 移动一位到 2，fast 移动两位到 3
# 由于 3.next.next 为空，所以跳出 while，此时 slow 指向了中间节点前的那个节点
# 如果链表长度为奇数，则 slow 指向了中间节点
# 比如链表为 1 --> 2 --> 3
# 一开始，slow 和 fast 同时指向 1，slow 移动一位到 2，fast 移动两位到 3
# 由于 3.next 为空，所以跳出 while，此时 slow 指向了中间节点
while fast.next != None and fast.next.next != None :
# slow 这个指针每次都向后移动一步
slow = slow.next
# fast 这个指针每次都向后移动两步
fast = fast.next.next
# 这个时候，slow 指向的那个节点把链表划分为两个区域
# 翻转右区域的链表
# 获取右区域的链表翻转之后的头节点
rightHead = self.reverseList(slow.next)
# 获取左区域的链表的头节点
leftHead = head
# 让 leftHead 和 rightHead 同时向后移动，直到 rightHead 指向 None 为止
# 说明比较完了所有的节点
while rightHead != None :
# 如果它们的节点值不一样，那么就不是回文链表
if leftHead.val != rightHead.val :
# 不是回文链表，返回 False
return False
# 否则，让 rightHead 继续向右移动
rightHead = rightHead.next
# 否则，让 rightHead 继续向右移动
leftHead = leftHead.next
# 比较完所有的节点，说明是回文链表，返回 true
return True
# 反转链表的代码
def reverseList(self,head:ListNode) -> ListNode:
# 寻找递归终止条件
# 1、head 指向的结点为 None
# 2、head 指向的结点的下一个结点为 None
# 在这两种情况下，反转之后的结果还是它自己本身
if head == None or head.next == None:
return head
# 不断的通过递归调用，直到无法递归下去，递归的最小粒度是在最后一个节点
# 因为到最后一个节点的时候，由于当前节点 head 的 next 节点是空，所以会直接返回 head
cur = self.reverseList(head.next)
# 比如原链表为 1 --> 2 --> 3 --> 4 --> 5
# 第一次执行下面代码的时候，head 为 4，那么 head.next = 5
# 那么 head.next.next 就是 5.next ，意思就是去设置 5 的下一个节点
# 等号右侧为 head，意思就是设置 5 的下一个节点是 4
# 这里出现了两个 next
# 第一个 next 是「获取」 head 的下一节点
# 第二个 next 是「设置」 当前节点的下一节点为等号右侧的值
head.next.next = head
# head 原来的下一节点指向自己，所以 head 自己本身就不能再指向原来的下一节点了
# 否则会发生无限循环
head.next = None
# 我们把每次反转后的结果传递给上一层
return cur
