234. Palindrome Linked List

  • 32.0%

https://leetcode.com/problems/palindrome-linked-list/#/description

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?


方法一:

将后半部分进行反转链表,则与前半部分应该是相同的。

所以第一步找到中间点,第二步反转,第三步进行比较。

https://discuss.leetcode.com/topic/18304/share-my-c-solution-o-n-time-and-o-1-memory

Share my C++ solution, O(n) time and O(1) memory

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head==NULL||head->next==NULL)
return true;
ListNode* slow=head;
ListNode* fast=head;
while(fast->next!=NULL&&fast->next->next!=NULL){
slow=slow->next;
fast=fast->next->next;
}
slow->next=reverseList(slow->next);
slow=slow->next;
while(slow!=NULL){
if(head->val!=slow->val)
return false;
head=head->next;
slow=slow->next;
}
return true;
}
ListNode* reverseList(ListNode* head) {
ListNode* pre=NULL;
ListNode* next=NULL;
while(head!=NULL){
next=head->next;
head->next=pre;
pre=head;
head=next;
}
return pre;
}
};

我的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head || !head->next) return true;
ListNode* fast = head, *slow = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
ListNode* cur = slow->next;
slow->next = NULL;
while(cur){
ListNode* nex = cur->next;
cur->next = slow->next;
slow->next = cur;
cur = nex;
}
fast = head;
slow = slow->next;
while(slow){
if(fast->val != slow->val)
return false;
fast = fast->next;
slow = slow->next;
}
return true;
}
};

https://discuss.leetcode.com/topic/27605/my-easy-understand-c-solution

My easy understand C++ solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode* temp;
bool isPalindrome(ListNode* head) {
temp = head;
return check(head);
}

bool check(ListNode* p) {
if (NULL == p) return true;
bool isPal = check(p->next) & (temp->val == p->val);
temp = temp->next;
return isPal;
}
};

https://discuss.leetcode.com/topic/18533/reversing-a-list-is-not-considered-o-1-space

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.


https://discuss.leetcode.com/topic/18293/11-lines-12-with-restore-o-n-time-o-1-space/2

11 lines, 12 with restore, O(n) time, O(1) space

O(n) time, O(1) space. The second solution restores the list after changing it.

Solution 1: Reversed first half == Second half?

Phase 1: Reverse the first half while finding the middle.

Phase 2: Compare the reversed first half with the second half.

1
2
3
4
5
6
7
8
9
10
11
12
def isPalindrome(self, head):
rev = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
if fast:
slow = slow.next
while rev and rev.val == slow.val:
slow = slow.next
rev = rev.next
return not rev

Solution 2: Play Nice

Same as the above, but while comparing the two halves, restore the list to its original state by reversing the first half back. Not that the OJ or anyone else cares.

1
2
3
4
5
6
7
8
9
10
11
12
13
def isPalindrome(self, head):
rev = None
fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, head = head, rev, head.next
tail = head.next if fast else head
isPali = True
while rev:
isPali = isPali and rev.val == tail.val
head, head.next, rev = rev, head, rev.next
tail = tail.next
return isPali

https://discuss.leetcode.com/topic/18952/python-easy-to-understand-solution-with-comments-operate-nodes-directly

Python easy to understand solution with comments (operate nodes directly).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def isPalindrome(self, head):
fast = slow = head
# find the mid node
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# reverse the second half
node = None
while slow:
nxt = slow.next
slow.next = node
node = slow
slow = nxt
# compare the first and second half nodes
while node: # while node and head:
if node.val != head.val:
return False
node = node.next
head = head.next
return True

https://discuss.leetcode.com/topic/18301/5-lines-python-o-n-time-and-space

5 lines Python, O(n) time and space

I just realized that the O(1) space is only a follow-up, so here’s the obvious one without that.

1
2
3
4
5
6
def isPalindrome(self, head):
vals = []
while head:
vals += head.val,
head = head.next
return vals == vals[::-1]
谢谢你,可爱的朋友。