solving the problem three steps: find the middle position+ reverse the second part + compare


  • 0
    L

    Hope it will help you. The most tricky part for me is the method i used is like [1,..., n] mid = 1+ (n-1)/2, it is left tended. By doing ListNode cur = slow.next, the length of right part of the nodes will be less or equal to that of left.

    /**
     * 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) {
            ListNode fast = head, slow = head;
            if(head == null) return true;
            
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode cur = slow.next;
            slow.next = null;
            ListNode pre = null;
            while(cur != null){
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            ListNode st1 = pre;
            ListNode st2 = head;
            while(st1 != null){
                if(st1.val != st2.val) return false;
                st1 = st1.next;
                st2 = st2.next;
            }
            return true;
        }
    }
    
    

Log in to reply
 

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