如何判断回文链表

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode 力扣 难度
234. Palindrome Linked List 234. 回文链表 🟢
- 剑指 Offer II 027. 回文链表 🟢

———–

前文 数组双指针技巧汇总 和 子序列问题解题思路 讲解了回文串和回文序列相关的问题，先来简单回顾下。

寻找回文串的核心思想是从中心向两端扩展：

// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
String palindrome(String s, int left, int right) {
    // 防止索引越界
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        // 双指针，向两边展开
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s.substring(left + 1, right);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
string palindrome(string s, int left, int right) {
    // 防止索引越界
    while (left >= 0 && right < s.length()
            && s[left] == s[right]) {
        // 双指针，向两边展开
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s.substr(left + 1, right - left - 1);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def palindrome(s: str, left: int, right: int) -> str:
    # 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
    # 防止索引越界
    while left >= 0 and right < len(s) and s[left] == s[right]:
        # 双指针，向两边展开
        left -= 1
        right += 1
    # 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s[(left + 1):right]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

//在s中寻找以s[left]和s[right]为中心的最长回文串
func palindrome(s string, left int, right int) string {
    //防止索引越界
    for left >= 0 && right < len(s) && s[left] == s[right] {
        //双指针，向两边展开
        left--
        right++
    }
    //返回以s[left]和s[right]为中心的最长回文串
    return s[left+1 : right]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var palindrome = function(s, left, right) {
    // 防止索引越界
    while (left >= 0 && right < s.length && s.charAt(left) == s.charAt(right)) {
        // 双指针，向两边展开
        left--;
        right++;
    }
    // 返回以 s[left] 和 s[right] 为中心的最长回文串
    return s.substring(left + 1, right);
};

因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入 l 和 r。

而判断一个字符串是不是回文串就简单很多，不需要考虑奇偶情况，只需要 双指针技巧，从两端向中间逼近即可：

boolean isPalindrome(String s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

bool isPalindrome(string s) {
    //一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) { //判断左右指针对应字符是否相等
            return false;
        }
        left++;
        right--;
    }
    return true;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def isPalindrome(s: str) -> bool:
    # 一左一右两个指针相向而行
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 将给定的字符串 s 转换成小写字母，并剔除其字母以外的字符
func isPalindrome(s string) bool {
    s = strings.ToLower(s) // 转换成小写字母
    left, right := 0, len(s)-1 // 一左一右两个指针相向而行
    for left < right {
        if !unicode.IsLetter(rune(s[left])) { // 剔除左指针不是字母的字符
            left++
            continue
        }
        if !unicode.IsLetter(rune(s[right])) { // 剔除右指针不是字母的字符
            right--
            continue
        }
        if s[left] != s[right] { // 比较左右指针是否相等
            return false
        }
        left++
        right--
    }
    return true
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 使用 var 关键字声明函数 isPalindrome，参数为字符串 s
var isPalindrome = function(s) {
  // 左右两个指针相向而行
  let left = 0, right = s.length - 1;
  while (left < right) {
    // 若左右指针的值不相同，则 s 不是回文字符串
    if (s.charAt(left) !== s.charAt(right)) {
        return false;
    }
    left++;
    right--;
  }
  // 否则 s 是回文字符串
  return true;
};

以上代码很好理解吧，因为回文串是对称的，所以正着读和倒着读应该是一样的，这一特点是解决回文串问题的关键。

下面扩展这一最简单的情况，来解决：如何判断一个「单链表」是不是回文。

一、判断回文单链表

看下力扣第 234 题「 回文链表」：

输入一个单链表的头结点，判断这个链表中的数字是不是回文，函数签名如下：

boolean isPalindrome(ListNode head);

比如说：

输入: 1->2->null
输出: false

输入: 1->2->2->1->null
输出: true

这道题的关键在于，单链表无法倒着遍历，无法使用双指针技巧。

那么最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。关于如何反转链表，可以参见前文 递归翻转链表的一部分。

其实，借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表，下面来具体聊聊。

对于二叉树的几种遍历方式，我们再熟悉不过了：

void traverse(TreeNode root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

void traverse(TreeNode* root) {
    // 前序遍历代码
    traverse(root->left);
    // 中序遍历代码
    traverse(root->right);
    // 后序遍历代码
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def traverse(root: TreeNode) -> None:
    # 前序遍历代码
    traverse(root.left)
    # 中序遍历代码
    traverse(root.right)
    # 后序遍历代码

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func traverse(root *TreeNode) {
    // 前序遍历代码
    traverse(root.left)
    // 中序遍历代码
    traverse(root.right)
    // 后序遍历代码
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var traverse = function(root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
};

在 学习数据结构的框架思维 中说过，链表兼具递归结构，树结构不过是链表的衍生。那么，链表其实也可以有前序遍历和后序遍历：

void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

void traverse(ListNode* head) {
    // 前序遍历代码
    traverse(head->next);
    // 后序遍历代码
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def traverse(head: ListNode):
    # 前序遍历代码
    traverse(head.next)
    # 后序遍历代码

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func traverse(head *ListNode) {
   // 前序遍历代码
   traverse(head.Next)
   // 后序遍历代码
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var traverse = function(head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

这个框架有什么指导意义呢？如果我想正序打印链表中的 val 值，可以在前序遍历位置写代码；反之，如果想倒序遍历链表，就可以在后序遍历位置操作：

/* 倒序打印单链表中的元素值 */
void traverse(ListNode head) {
    if (head == null) return;
    traverse(head.next);
    // 后序遍历代码
    print(head.val);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/* 倒序打印单链表中的元素值 */
void traverse(ListNode* head) {
    if (head == NULL) return;
    traverse(head->next);
    // 后序遍历代码
    print(head->val);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

# 倒序打印单链表中的元素值
def traverse(head: ListNode):
    if head is None:
        return
    traverse(head.next)
    # 后序遍历代码
    print(head.val)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 倒序打印单链表中的元素值
func traverse(head *ListNode) {
    if head == nil {
        return
    }
    traverse(head.Next)
    // 后序遍历代码
    print(head.Val)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

/**
 * 倒序打印单链表中的元素值
 */
function traverse(head) {
  if (head === null) {
    return;
  }
  traverse(head.next);
  // 后序遍历代码
  console.log(head.val);
}

说到这了，其实可以稍作修改，模仿双指针实现回文判断的功能：

// 左侧指针
ListNode left;

boolean isPalindrome(ListNode head) {
    left = head;
    return traverse(head);
}

boolean traverse(ListNode right) {
    if (right == null) return true;
    boolean res = traverse(right.next);
    // 后序遍历代码
    res = res && (right.val == left.val);
    left = left.next;
    return res;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 左侧指针
ListNode* left;

bool isPalindrome(ListNode* head) {
    left = head;
    return traverse(head);
}

bool traverse(ListNode* right) {
    if (right == nullptr) return true;
    bool res = traverse(right->next);
    // 后序遍历代码
    res = res && (right->val == left->val);
    left = left->next;
    return res;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 左侧指针
left = None

def isPalindrome(head: ListNode) -> bool:
    global left
    left = head
    return traverse(head)

def traverse(right: ListNode) -> bool:
    global left
    if right is None:
        return True
    res = traverse(right.next)
    # 后序遍历代码
    res = res and (right.val == left.val)
    left = left.next
    return res

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isPalindrome(head *ListNode) bool {
    var traverse func(*ListNode, *ListNode) bool
    traverse = func(right, left *ListNode) bool {
        if right == nil {
            return true
        }
        res := traverse(right.Next, left)
        // 后序遍历代码
        res = res && (right.Val == left.Val)
        *left = *(*left).Next
        return res
    }
    
    left := &head
    return traverse(head, left)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

// 左侧指针
var left;

// 判断链表是否是回文结构
function isPalindrome(head) {
    left = head;
    return traverse(head);
}

// 遍历链表
function traverse(right) {
    if (right == null) return true;
    var res = traverse(right.next);
    // 后序遍历代码
    res = res && (right.val == left.val);
    left = left.next;
    return res;
}

这么做的核心逻辑是什么呢？实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已，如下 GIF 所示：

当然，无论造一条反转链表还是利用后序遍历，算法的时间和空间复杂度都是 O(N)。下面我们想想，能不能不用额外的空间，解决这个问题呢？

二、优化空间复杂度

更好的思路是这样的：

1、先通过 双指针技巧 中的快慢指针来找到链表的中点：

ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow 指针现在指向链表中点

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* slow, *fast;
slow = fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow 指针现在指向链表中点

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow 指针现在指向链表中点

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var slow, fast *ListNode
slow, fast = head, head
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
}
//slow 现在指向链表的中点

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var slow, fast;
slow = fast = head;
while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow 指针现在指向链表中点

2、如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：

if (fast != null)
    slow = slow.next;

3、从slow开始反转后面的链表，现在就可以开始比较回文串了：

ListNode left = head;
ListNode right = reverse(slow);

while (right != null) {
    if (left.val != right.val)
        return false;
    left = left.next;
    right = right.next;
}
return true;

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

ListNode* left = head;
ListNode* right = reverse(slow);

while (right != nullptr) {
    if (left->val != right->val)
        return false;
    left = left->next;
    right = right->next;
}
return true;

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

left, right = head, reverse(slow)

while right:
    if left.val != right.val:
        return False
    left, right = left.next, right.next

return True

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

left := head
right := reverse(slow)

for right != nil {
    if left.Val != right.Val {
        return false
    }
    left = left.Next
    right = right.Next
}

return true

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var isPalindrome = function(head) {
    let left = head;
    let right = reverse(findMid(head));

    while (right !== null) {
        if (left.val !== right.val) {
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
};

至此，把上面 3 段代码合在一起就高效地解决这个问题了，其中 reverse 函数很容易实现：

boolean isPalindrome(ListNode head) {
    ListNode slow, fast;
    slow = fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (fast != null)
        slow = slow.next;
    
    ListNode left = head;
    ListNode right = reverse(slow);
    while (right != null) {
        if (left.val != right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    
    return true;
}

ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

bool isPalindrome(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    if (fast != nullptr)
        slow = slow->next;
    
    ListNode* left = head;
    ListNode* right = reverse(slow);
    while (right != nullptr) {
        if (left->val != right->val)
            return false;
        left = left->next;
        right = right->next;
    }
    
    return true;
}

ListNode* reverse(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def isPalindrome(head: ListNode) -> bool:
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    if fast:
        slow = slow.next
        
    left, right = head, reverse(slow)

    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

def reverse(head: ListNode) -> ListNode:
    pre, cur = None, head

    while cur:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next

    return pre

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func isPalindrome(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    
    if fast != nil {
        slow = slow.Next
    }
    
    left, right := head, reverse(slow)
    for right != nil {
        if left.Val != right.Val {
            return false
        }
        left = left.Next
        right = right.Next
    }
    return true
}

func reverse(head *ListNode) *ListNode {
    var prev, cur *ListNode = nil, head
    for cur != nil {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var isPalindrome = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (fast)
        slow = slow.next;
    
    let left = head,
        right = reverse(slow);
    
    while (right) {
        if (left.val !== right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    
    return true;
}

var reverse = function(head) {
    let pre = null, cur = head;
    while (cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

算法过程如下 GIF 所示：

🎃 代码可视化动画 🎃

算法总体的时间复杂度 O(N)，空间复杂度 O(1)，已经是最优的了。

我知道肯定有读者会问：这种解法虽然高效，但破坏了输入链表的原始结构，能不能避免这个瑕疵呢？

其实这个问题很好解决，关键在于得到p, q这两个指针位置：

这样，只要在函数 return 之前加一段代码即可恢复原先链表顺序：

p.next = reverse(q);

篇幅所限，我就不写了，读者可以自己尝试一下。

三、最后总结

首先，寻找回文串是从中间向两端扩展，判断回文串是从两端向中间收缩。对于单链表，无法直接倒序遍历，可以造一条新的反转链表，可以利用链表的后序遍历，也可以用栈结构倒序处理单链表。

具体到回文链表的判断问题，由于回文的特殊性，可以不完全反转链表，而是仅仅反转部分链表，将空间复杂度降到 O(1)。

最后打个广告，我亲自制作了一门 数据结构精品课，以视频课为主，手把手带你实现常用的数据结构及相关算法，旨在帮助算法基础较为薄弱的读者深入理解常用数据结构的底层原理，在算法学习中少走弯路。

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode 力扣
- 剑指 Offer II 027. 回文链表

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释