README.md

234. 回文链表

English Version

题目描述

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True
        mid = self.find_mid_node(head)
        second_half_list = self.reverse_list(mid.next)
        result = True
        p, q = head, second_half_list
        while result and q:
            if p.val != q.val:
                result = False
            else:
                p, q = p.next, q.next
        mid.next = self.reverse_list(second_half_list)
        return result
        
    def reverse_list(self, head):
        pre, p = None, head
        while p:
            q = p.next
            p.next = pre
            pre = p
            p = q
        return pre
    
    def find_mid_node(self, head):
        slow = fast = head
        while fast.next and fast.next.next:
            slow, fast = slow.next, fast.next.next
        return slow

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode mid = findMidNode(head);
        ListNode secondHalfList = reverseList(mid.next);
        boolean result = true;
        ListNode p = head, q = secondHalfList;
        while (result && q != null) {
            if (p.val != q.val) {
                result = false;
            } else {
                p = p.next;
                q = q.next;
            }
        }
        mid.next = reverseList(secondHalfList);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null, p = head;
        while (p != null) {
            ListNode q = p.next;
            p.next = pre;
            pre = p;
            p = q;
        }
        return pre;
    }

    private ListNode findMidNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

...