leetcode [#234]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given a singly linked list, determine if it is a palindrome.

---

解决方案

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isPalindrome(ListNode head) {
        boolean result = true;
        if(head == null) return result;
        
        ListNode p = head;
        List<Integer> list = new ArrayList<>();

        while (p != null){
            list.add(p.val);
            p = p.next;
        }
        p = head;

        for(int i = list.size()-1; i >= 0; i--){
            if(list.get(i) != p.val){
                result = false;
                break;
            }
            p = p.next;
        }
        return result;
    }
}

---

注意事项

1. 一共遍历了两遍，第一遍把所有值存起来；第二遍将存起来的值倒序和链表中每个值比较。
2. 该方法效率较低，更好的方法如下：

   public boolean isPalindrome(ListNode head) {
       ListNode fast = head;
       ListNode slow = head;
   
       while(fast != null && fast.next != null) {
           fast = fast.next.next;
           slow = slow.next;
       }
       if(fast != null) slow = slow.next;
   
       slow = reverse(slow);
       while(slow != null && head.val == slow.val) {
           head = head.next;
           slow = slow.next;
       }
       return slow == null;
   }
   private ListNode reverse(ListNode head) {
       ListNode prev = null;
       while(head != null) {
           ListNode next = head.next;
           head.next = prev;
           prev = head;
           head = next;
       }
       return prev;
   }

该方法中包含了很常用的链表翻转方法：

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