5 lines Python, O(n) time and space


  • 11

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

    def isPalindrome(self, head):
        vals = []
        while head:
            vals += head.val,
            head = head.next
        return vals == vals[::-1]

  • 0
    D
      public boolean isPalindrome(ListNode head) {
            if(head == null)
            	return true;
            
           
            ListNode slow = head;
            ListNode fast = head;
            
            while(fast != null && fast.next != null){
            	 fast = fast.next.next;
            	 slow = slow.next;
            }
            ListNode q = null;
            //there are even number of nodes in the list
            if(fast == null){
            	q = reverseList(slow);
            }
            //there are odd number of nodes in the list
            else if(fast.next == null){
            	q = reverseList(slow.next);
            }
            
            ListNode p = head;
            
            while(p != null && q != null){
            	if(p.val != q.val){
            		return false;
            	}
            	p = p.next;
            	q = q.next;
            }
            		
            
            return true;
        }
        
    	public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode before = null;
            ListNode p = head;
            
            while(p != null){
                ListNode next = p.next;
                p.next = before;
                before = p;
                p = next;
            }
            return before;
    	}
    

  • 0

    I don't understand. What does this have to do with mine?


  • 0

    Aha, after seeing the O(1) requirement, I just forgot such an idea.


  • 0

    Me, too. I only realized it when I was about to tell someone about it and double-checked :-)


  • 0
    S

    why does OJ tell me "Line 13: TypeError: 'int' object is not iterable"???
    (Line 13: vals += head.val, same as yours)


  • 0

    You probably forgot the comma.


  • 0

    that should be " vals += [head.val] ", it has nothing to do with the comma.


  • 0

    @songzy12 Huh? Why should it be a list instead of a tuple? Tuple is much faster for this (I tested it a while back and again now) and one fewer character to type. And what do you mean it has nothing to do with the comma? That comma makes the difference between working and not working, and probably the difference between my code and swordx's. Also, if you say that, then you should also say that it has nothing to do with your brackets. Sorry, but you make no sense.


  • 0

    Sorry I made a mistake. I didn't notice that the function of comma is to make it a tuple. I just mixed it with semicolon. Maybe I should learn more about python :) By the way, do "+= head.val, " and "+= [head.val] " only different ways to add element to a list ?


  • 0
    S

    Thanks, I tried to add a comma and you're right it worked. Actually I do not quite understand this usage either. Why do you say that it's a tuple? "vals" is a list and elements in it are integers, so which is tuple...? And what's the difference between"+= xxx,", "+= [xxx]" and ".append(xxx)"? Would you please show some references(urls) to explain this usage? Thanks again.


  • 0

    @swordx head.val is an int, head.val, is a tuple (containing just that int). I don't know a functional difference between "+= xxx,", "+= [xxx]" and ".append(xxx)", and I choose the tuple way because it's less code and fast. I thought it's the fastest of the three based on earlier testing, but new testing disagrees, so maybe it changed in the meantime or maybe I misremember. The test I just did appends three million ints to an empty list and I get times like these:

    append 0.44178211689
    list 0.684427022934
    tuple 0.499861001968

  • 0

    Not sure what kind of reference you're looking for, but here's a good page, I think.


  • 0

    @songzy12 Yeah, unnecessary semicolons irritate me a lot. See for example this and my answer there :-)

    "do "+= head.val, " and "+= [head.val] " only different ways to add element to a list ?"

    Sorry, I don't understand the question. Maybe my new reply to swordx answers your question as well?


  • 0
    D

    tuple is immutable. Is it the reason using tuple is faster?


  • 0

    I don't really know. I made a new test just creating lists and tuples, and tuples were similarly much faster at that. So apparently it's not the appending to the list but the creation of the list/tuple that makes the difference.

    Alex Martelli said a while back that "tuple construction [...] is about twice as fast as list construction -- and that discrepancy can be explained by the tuple's sheer simplicity". I don't know what he means with simplicity, but I guess its immutability could indeed play a role in that.


  • 0
    D

    Maybe you can check the source code here:
    http://svn.python.org/projects/python/trunk/Objects/

    I lost my patience after a while :)


  • 0

    Yeah, I looked into the C source a few times before and I don't have the patience for it, either :-)


  • 0
    B

    @swordx add a element to list can use "append(),extend(),insert(), +" in python ,and the "+"must list not int


  • 0
    R

    @StefanPochmann Sorry I am a newbie. Didn't understand your code very well. Could you please elaborate a little bit? What is the last return statement doing?


Log in to reply
 

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