DEV Community is a community of 787,570 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. 30-Day LeetCoding Challenge: Middle of the Linked List

Solution:

The problem is so straightforward and so clear it asks us to return the middle node, with one condition if there is two middle numbers return the second one.

If we think about it for a minute the two middle numbers only happen when the length of the array is even, but the fact is if we do integer division for len(arr) // 2 to get the middle number it will always give you the correct middle number, let's see it:

If we have arr = [1,2,3,4,5] then the middle number will be at len(arr) // 2 = 5 // 2 = 2 so it will be arr = 3 which is the correct middle number.

What if it is even arr = [1,2,3,4,5,6] so it will be len(arr) // 2 = 6 // 2 = 3 so ... arr == 4 which is the second middle number.

This should make the problem now easier so what we will do now based on the above we just want to put all our linked-list nodes in an array then return the middle node in that array (return nodes[len(nodes) // 2]).

• Example:

lked_list = 1 --> 2 --> 3 --> 4 --> 5

• First we will have nodes = [] array to store our nodes there.

• We need to start from the head and keep looping until the end and keep pushing to the array the elements

• So, at end our nodes array will be like this:

nodes = [{val: 1, next: ->}, {val: 2, next: ->}, {val: 3, next: ->}, {val: 4, next: ->}, {val: 5, next: None}]

• No our answer will be ans = nodes[len(nodes) // 2] = nodes[5 // 2] = ndes = {val: 3, next: ->}.

• Pseudocode:

1. define nodes = []
2. loop as long as head != None