CODEWITHSUNDEEP
pythondata-structureslinked-list
stillearning
stillearning

Reputation: 403

Understanding the while loop condition in how to find the middle node in a linked list

I don't fully understand the while loop condition for the "find the middle of linked list" question on leetcode:

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

For the while loop, I thought the condition would be

while first and last.next:

But when I do that, I receive an error that says

AttributeError: 'NoneType' object has no attribute 'next'

The condition statement is supposed to be

while last and last.next:

I don't understand why. Here is the entire code with the correct while loop:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def middleNode(self, head):
        first = last = head
        while last and last.next:
            first = first.next
            last = last.next.next
        return first

Upvotes: 3

Views: 954

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114320

The idea behind the algorithm is that you don't know where the end of the list is. However, if you step one pointer twice as fast as the other, it will reach the end just as the other reaches the middle.

The initialization sets the middle (first) and end (last) pointers to the only thing you know initially: the start of the list. The body of the loop steps them forward: first = first.next moves one step ahead while last = last.next.next moves two steps ahead. Since last is always ahead of first, the is no need to check if first can move forward. Instead, the condition of the loop checks that both of the references used in stepping last are non-None: while last and last.next:.

Notice that if the list has one element, last will not move since last.next is None. However, with two elements, last will move, and so will first. The result is that the condition for picking the second middle from a list with an even number of elements is satisfied.

Upvotes: 5

MarkReedZ
MarkReedZ

Reputation: 1437

Just draw it out and it will be obvious. Consider both versions:

A - B - C

first / last / last.next
A       B      C  
B       None

A - B - C - D

first / last / last.next
A       B      C  
B       D      None

Upvotes: 0

Related Questions