leetcode 234 palindrome linked list

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

Follow up:
Could you do it in O(n) time and O(1) space?

using two pointers:
- A slow pointer with step length equals One
- A fast pointer with step length eauqls Two
We can get the middle elements pointed by slow when the total number of the array is odd.
Slow pointer points at the larger one when the array is at a length of even.
We can implements an function which reverses the linked list, So we can get the reverse list over [slow, -1].
compare head with slow step by step until slow points to null.


 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class  {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow);
        while(slow!=null){
            if(slow.val != head.val){
                return false;
            }
            head = head.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;
    }
}

leetcode 234 palindrome linked list

近期文章

近期评论

标签

热门

文章归档

分类目录

功能