# 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.

``````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.

``````def isPalindrome(self, head):
rev = None
while fast and fast.next:
fast = fast.next.next
tail = head.next if fast else head
isPali = True
while rev:
isPali = isPali and rev.val == tail.val
tail = tail.next
return isPali``````

• Nice idea and concise code! Learn a lot. The swapping by `,` of Python is really powerful! `rev, rev.next, slow = slow, rev, slow.next` becomes the following 4 lines of codes in C++, much verbose :-)

``````ListNode* tmp = rev;
rev = slow;
slow = slow -> next;
rev -> next = tmp;
``````

Not that the OJ or anyone else cares.

Well, I believe the interviewer will care a lot...

• Hi, Stefan. Always glad to see your solutions.

Would you mind explaining the difference between

``````slow, slow.next, rev = slow.next, rev, slow
``````

and

``````rev, slow.next, slow = slow, rev, slow.next
``````

for me?

I used to think they are the same.

However, I got error message "Line 15: AttributeError: 'NoneType' object has no attribute 'next'" with the former while AC with the latter.

here is the whole code:

``````class Solution:
rev = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
# slow, slow.next, rev = slow.next, rev, slow
rev, slow.next, slow = slow, rev, slow.next
if fast:
slow = slow.next
while slow:
if slow.val != rev.val:
return False
slow, rev = slow.next, rev.next
return True
``````

Forgive my poor english...

• ``````slow, slow.next, rev = slow.next, rev, slow
``````

That first evaluates the right side and then assigns to the left side from left to right. So first, `slow` becomes what used to be `slow.next`. And then, `slow.next` gets assigned something, but that `slow` is already changed! So you're setting the `.next` of the wrong node. That's the difference to the first version.

But I'm still confused that the error message is "Line 15: AttributeError: 'NoneType' object has no attribute 'next'".
In this case[1,2,2,1], why the new `slow` become `NoneType` rather than `slow.next`(which is not None)?

• With the faulty code, in the second loop iteration `slow.next` is None. Just add `print slow.next` in the loop to see it.

• My mistake. I shouldn't assume the error happened in the first loop. I have learned a lot from you and caikehe ever since i came here. Thanks a lot!

• This post is deleted!

• YOUR second solution is really nice and wonful

• Thank you so much @StefanPochmann. I learned so much from you.

• Thanks!
I wrote a C++ version of your algorithm. Your algorithm is pretty brilliant. I failed to think of any one better.

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
bool isSameList(ListNode *node0, ListNode *node1) {
while(node0 && node1) {
if (node0->val != node1->val) return false;
node0 = node0->next;
node1 = node1->next;
}
//if (node0 || node1) return false;
return true;
}
public:
bool isPalindrome(ListNode* head) {
ListNode *pre = NULL, *fast = head, *slow = head;
while(fast && fast->next) {		//reverse list
fast = fast->next->next;
ListNode *tmp = slow;
slow = slow->next;
tmp->next = pre;
pre = tmp;
}
if(fast != NULL) {
slow = slow->next;
}
return isSameList(pre, slow);
}
};

``````

• Brilliant algorithm! Always expect your python solutions.

• I was about to post my 7-liner, but I found this post and think it's identical.

``````class Solution(object):
pre, cur, cur2 = None, head, head
while cur2 and cur2.next:
cur.next, pre, cur, cur2 = pre, cur, cur.next, cur2.next.next
n1, n2 = pre, cur.next if cur2 else cur
while n1 and n1.val==n2.val:
n1, n2 = n1.next, n2.next
return n1 is None
``````

• rev

awesome

• rev, rev.next, slow = slow, rev, slow.next

@StefanPochmann I have the same question as @huamingrui.
What is different in the case of `a, b = b, a` then? Following your explanation, wouldn't `b` end up with `b` in the end?

• @StefanPochmann I guess I understand it now. As you mentioned, `That first evaluates the right side`, so `b, a` on the right-hand side is a tuple with the value of b and a. Assigning `b` to `a` won't change the value of right-hand side, so `b` still get the right value. In the case of

rev, rev.next, slow = slow, rev, slow.next

Assigned values are references, hence the difference.

• If I made a little bit change on the first while loop:

while fast and fast.next:
fast = fast.next.next
rev = slow
rev.next = rev
slow = slow.next

it would not work for a simple case [1, 2], with Time Limit Exceeded error.

Any idea what is wrong here? I just changed one line of code to 3 lines.

• @jianchao.li.fighter Thank you for adding those additional lines! I was very confused with what python was doing there.

• ``````        rev, rev.next, slow = slow, rev, slow.next
``````

This line is so elegant! Thank you!

• I don't understand why this does not work:

``````rev, rev.next = slow, rev
slow = slow.next
``````

Shouldn't this have the same effect as the one-liner used in code:
`rev, rev.next, slow = slow, rev, slow.next`
as we are not modifying `slow` before assigning `slow.next` to itself.

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