Could you do it in O(n) time and O(1) space?
public boolean isPalindrome(ListNode head) { if(head == null) return true; ListNode slow = head, fast = head; while(
fast.next!=null && fast.next.next != null
){ slow = slow.next; fast = fast.next.next; } //这里的slow指向的是前半个list的最后一个点(前半个list的长度可能比后半个大1)
slow.next = reverse(slow.next); slow = slow.next;
while(slow!=null){ if(slow.val != head.val) return false; slow = slow.next; head = head.next; } return true; }
没有评论:
发表评论