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?
Subscribe to see which companies asked this question.
思路：获得链表的长度，逆置其中的后半部分的链表，对比两个链表
public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } // 获得链表的长度 int len = 0; ListNode listNode = head; while (listNode != null) { len++; listNode = listNode.next; } int l = len / 2 - 1; ListNode p1, p2; p1 = head; p2 = p1.next; l--; while (l-- > 0) { p1 = p2; p2 = p2.next; } // 当链表的长度是奇数的时候 if (len % 2 != 0) { p2 = p2.next; } // 逆置链表的一般 p1.next = null; ListNode q1; q1 = p2.next; p2.next = null; while (q1 != null) { ListNode t = q1.next; q1.next = p2; p2 = q1; q1 = t; } // 比较两个链表 while (p2 != null && head != null) { if (p2.val != head.val) { return false; } p2 = p2.next; head = head.next; } return true; }
但是LeetCode里面的大神说逆置链表的方法都不控件复杂度为O(1)的方法，因为有一个先决条件，就是输入的条件应该是只读的，逆置链表则进行了写操作。
Reversing a list is not considered "O(1) space"It is a common misunderstanding that the space complexity of a program is just how much the size of additional memory space being used besides input. An important prerequisite is neglected the above definition: the input has to be read-only. By definition, changing the input and change it back is not allowed (or the input size should be counted when doing so). Another way of determining the space complexity of a program is to simply look at how much space it has written to. Reversing a singly linked list requires writing to O(n) memory space, thus the space complexities for all "reverse-the-list"-based approaches are O(n), not O(1).
Solving this problem in O(1) space is theoretically impossible due to two simple facts: (1) a program using O(1) space is computationally equivalent to a finite automata, or a regular expression checker; (2) the pumping lemma states that the set of palindrome strings does not form a regular set.
Please change the incorrect problem statement.
