My java 1ms solution with reverse half list


  • 11
    P
    /**
     * 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) {
            if(head == null) {
                return true;
            }
            //1.遍历确定长度
            int length = 0;
            ListNode p = head;
            while(p != null) {
                length ++;
                p = p.next;
            }
            p = head;//用完之后, p归位
            if(length == 1) {
                return true;
            }
            //2.将后半部分链反转
            int half = (length + 1) / 2;
            ListNode q = head;
            for(int i = 0; i < half; i ++) {
                q = q.next;
            }
            //开始反转
            ListNode r = q.next;
            q.next = null;
            ListNode m;
            while(r != null) {
                m = r.next;
                r.next = q;
                q = r;
                r = m;
            }
            //3.依次比较,直到其中一个或者两个链遍历完
            while(q != null && p != null) {
                if(p.val == q.val) {
                    q = q.next;
                    p = p.next;
                }else {
                    return false;
                }
                
            }
            return true;
        }
    }

  • -1

    这个问题不能在 O(n) time and O(1) space 里解决吗?


  • 0
    P

    现在这个解法就是O(n)tme和O(1)space的呀


Log in to reply
 

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