Linked list: While fast and fast.next

user_16065150 0
Viewed 550

I am learning the following code for Middle of Linked List:

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

I noticed that if I use "while fast.next" instead of "while fast and fast.next" for the loop, I got the same results. May I ask why I should use both fast and fast.next to stop the while loop? From my understanding, if fast.next is None, fast is always none, is this correct?

Thank you!

linked-list python
2 Answers

I noticed that if I use while fast.next instead of while fast and fast.next for the loop, I got the same results.

This will work for input lists that have an odd number of nodes, but it will fail withe input lists that have an even number of nodes -- the trivial example being an empty list (with 0 nodes).

May I ask why I should use both fast and fast.next to stop the while loop?

In each iteration a pair of nodes is traversed, so in the case of an even number of nodes, there will come a situation where fast is None at the moment the while condition is evaluated. If you then only check fast.next -- without first ensuring that fast is really a node -- it will raise an error, as this really means you're doing None.next which of course doesn't work.

From my understanding, if fast.next is None, fast is always none, is this correct?

No, this is not correct. If fast.next is None then this implies that fast is a node with a next attribute, so certainly fast is then not None. But fast.next can produce an error when fast is None. It is for that reason that before evaluating fast.next one must be sure that fast is a node and not None.

If the condition is fast and fast.next and it happens that fast is None then the evaluation will short-circuit and fast.next will not be evaluated at all (and that's what you want to avoid an error). This is because the and operation is already sure to evaluate to a falsy value when the left-side operand (fast) has been evaluated to be None.

user_54598390

As you traverse the linked list, and have a fast pointer that advances to the current node's next to next node, you have to make that check. Since the last node will have None (null) value for its next member variable, and if accessed simply as fast.next.next it leads to null pointer exception(NPE). To avoid it, your loop condition must be as you have it right now.

user_149737430
Related