给出一个单链表，确定它是否是回文☆☆☆☆

让我们来看一个例子[1, 1, 2, 1]。首先，设置两个指针，fast并slow从头开始。

1 -> 1 -> 2 -> 1 -> null
sf

（1）移动： fast指针移至末尾，并slow移至中间。

1 -> 1 -> 2 -> 1 -> null
          s          f

（2）反向：右半部分反向，slow指针变为第二个头。

1 -> 1    null <- 2 <- 1
h                      s

（3）比较：运行两个指针head，并slow一起进行比较。

1 -> 1    null <- 2 <- 1
     h            s

实现方式：

爪哇

public boolean isPalindrome(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    if (fast != null) { // odd nodes: let right half smaller
        slow = slow.next;
    }
    slow = reverse(slow);
    fast = head;

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

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Y

# Note: while comparing the two halves, restore the list to its original 
# state by reversing the first half back.

def isPalindrome(self, head):
    rev = None
    fast = head
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, head = head, rev, head.next
    tail = head.next if fast else head
    isPali = True
    while rev:
        isPali = isPali and rev.val == tail.val
        head, head.next, rev = rev, head, rev.next
        tail = tail.next
    return isPali

常见问题FAQ