LeetCode：234. Palindrome Linked List 回文链表

野性酷女 2021-06-24 16:11 336阅读 0赞

**试题：**  
Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2  
Output: false  
Example 2:

Input: 1->2->2->1  
Output: true

**代码：**  
显然由于链表的特性，我们需要找到中点，可以使用快慢指针来寻找，然后需要将前半段进行链表反转。最后再进行比较。

class Solution {
        private ListNode reverse(ListNode head){
            ListNode current = head, next = null, prev = null;
            while(current != null){
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            return prev;
        }
        private ListNode partition(ListNode head){
            ListNode fast = head.next, slow = head;
            while(fast != null){
                fast = fast.next;
                if(fast != null){
                    fast = fast.next;
                    slow = slow.next;
                }
            }
            ListNode second = slow.next;
            slow.next = null;
            return second;
        }
        private boolean areSame(ListNode a, ListNode b){
            while(a != null && b != null){
                if(a.val != b.val) return false;
                a = a.next;
                b = b.next;
            }
            return true;
        }
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
            ListNode second = reverse(partition(head));
            return areSame(head, second);
        }
    }