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


  • 117

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

  • 10

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


  • 7
    H

    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:
        def isPalindrome(self, head):
            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...


  • 12
    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.


  • 1
    H

    Thanks for your reply!
    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)?


  • 0

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


  • 0
    H

    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!


  • 0
    Y
    This post is deleted!

  • 0

    YOUR second solution is really nice and wonful


  • 0
    W

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


  • 3

    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);
        }
    };
    
    

  • 0
    Z

    Brilliant algorithm! Always expect your python solutions.


  • 0
    O

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

    class Solution(object):
        def isPalindrome(self, head):
            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
    

  • 0
    M

  • 0
    W

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

    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?


  • 0
    W

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


  • 0
    C

    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.


  • 0
    A

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


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

    This line is so elegant! Thank you!


  • 2
    A

    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.


Log in to reply
 

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