My easy understand java solution beats 98.58% of java submissions!


  • 0
    C
    • first we traversal the linkedlist O(n).
    • find the half length.
    • reverse the second half linkedlist locally.
    • compare the first half with second half.
    /**
     * 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;
            int len = 0;
            int steps = 0;
            ListNode temp = head;
            while(temp!=null){
            	len++;
            	temp=temp.next;
            }
            ListNode first = head;
            ListNode second = null;
            int compareTimes = 0;
            if(len%2==0){
            	steps = len/2;	
            	compareTimes = steps;
            }else{
            	steps = len/2+1;
            	compareTimes = steps-1;
            }
            temp = head;
            while(steps>0){
            	temp = temp.next;
            	steps--;
            }
            //链表就地逆序
            second = temp;
            ListNode tempHead = new ListNode(0);
            tempHead.next = null;
            while(second!=null){
            	//抽出r
            	ListNode r = second;
            	second = second.next;
            	//放在首节点后面
            	r.next = tempHead.next;
            	tempHead.next=r;
            }
            
            ListNode followNode = tempHead.next;
            while(compareTimes>0){
            	if(first.val!=followNode.val)return false;
            	first = first.next;
            	followNode = followNode.next;
            	compareTimes--;
            }
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.