Is this solution cheating? (No extra space and no two pointers)


  • 2
    D
    while head and head.next:
        if not head.next.val:
            return True
        head.val = None
        head = head.next
    return False
    

    Basically progress through the nodes and override all node values with None until the value of your next node is None. If you reach the last node without returning True, then there can be no cycle. The problem is that I'm unsure if you're allowed to change node values and that I'm assuming all nodes are initiated with "non-None" values.


  • -1
    C

    Yeah this is cheating actually :) The vals are your extra space.

    It's very similar to the idea that create a float array when dealing with integers, and save some extra information in the decimal part. The decimal part is indeed extra space.

    Nice try though :)


  • 0
    D

    This solution depends on the fact that no 'None' val in the linked list. Maybe you can replace 'None' val by "#". But still, maybe there is '#' already...


  • 0
    D

    I think you didn't check the solution carefully, there is no new variable created to store vals.
    All the vals are stored in the linked list itself. So the author is correct about no extra space.


  • 0
    C

    You didn't quite understand what I'm saying. I think we should assume the vals in the linked list are meaningful and should not be changed.


  • 0
    D

    Your expression is indeed not clear. If you say "the vals are extra space", you are wrong. If you assume the vals in linked list should not be changed, well, that is your own assumption. LeetCode OJ always mention such restriction explicitly. So I don't know what you expect me to understand from you.


Log in to reply
 

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