Middle of the Linked List

Given the first node in a linked list, get the node which represents the middle of the list. If there are two middle nodes, ie when there is an even number of nodes, return the second node.

To solve this, you use two iterators: one which moves +1 each iteration and another which moves +2. f(x) = x + 1, g(x) = x + 2. When the second reaches a null value, points to nothing, we know that the linked list terminated, and the first iterator represents half the number of iterations, which is the middle node.

Here, I will represent iterator 1 with a * and iterator 2 with a ^

In addition, if we know that the second iterator’s next value is null, the linked list iterations also terminates and that means the first iterator’s next value is the second middle node.

Pseudocode

function get middle
    iterator 1 = head
    iterator 2 = head.next
    while iterator2 is not null and iterator2's next is not null
        move iterator 1 by 1
        move iterator 2 by 2
    if iterator2 is null
        return iterator 1
    else
        return iterator 2

Python

This is what the code would look like.

    def getMiddle(self, head)
        it1 = head
        if(head.next == None):
            return head
        it2 = head.next
        while(it2 != None and it2.next != None):
            it1 = it1.next
            it2 = it2.next.next
        if(it2 == None):
            return it1
        else:
            return it1.next

Results

Success

Details

Runtime: 35 ms, faster than 88.16% of Python3 online submissions for Middle of the Linked List.

Memory Usage: 13.9 MB, less than 11.58% of Python3 online submissions for Middle of the Linked List.

Complexity Analysis:

Time Complexity: O(N)

Space Complexity: O(N)