Leet Code 876. Middle of the Linked List — Explained Python3 Solution

Photo by Ricky Kharawala on Unsplash

Problem Description

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.

Example 1:

Input: [1,2,3]
Output: Node 2 from this list (Serialization: [2,3])
The returned node has value 3.  (The judge's serialization of this node is [2,3]).

Example 2:

Input: [1,2,3,4]
Output: Node 3 from this list (Serialization: [3,4])
Since the list has two middle nodes with values 2 and 3, I return the second one.

Solution

There are basically 2 ways to tackle this problem. One is obvious to scan the link twice: the first time to get the total number of nodes, then I can divide it by 2 to get the middle index, a second scan will be run to find the middle index to return. The other way to do it is using one time scan: I can use 2 movers (fast and slow ones), in each iteration, slow mover will only move to the next node while fast one will move to the next of the next node. I will explain the second way more thoroughly in below.

The tricky part of the problem is that I am asked to return the second middle one if there are two (for example, return 3 for [1,2,3,4]). Basically there will be 2 senarioes, the length of input is even or odd. And certainly I need to verify some concern case like if the length is 1.

Below graph shows 2 senarioes, in odd input length scenario, fast mover can be on the edge of None. Take a look at the first one, at that moment, both slow and fast mover just move by 1 iteration. Now I should stop and return slow mover’s position since fast mover’s next is None. For the second one, slow mover is at index 2 while fast mover already points to None. Again, at this moment, there is no need to continue and what slow mover points to is exactly the second middle element.

Again, verify the corner case of input’s length is 1. It’s like above senario 1 (which total length is odd) except the movement step is 0 (not yet move). And like above description in senario 1, fast mover’s next is None, so no need to do anything more, just return slow mover (which is still in the very beginning of index 0).

Now let me show the codes:

Time & Space Complexity

I need to visit all elements in the list so assuming N is the number of elements in the list, time complexity will be O(N). There is no additional space scaled with N, only 2 pointers are used so the space complexity is static hence the space complexity is O(1).

Python 3 knowledge points

There is an interesting line in above solution, which is

fastMover, slowMover = head, head

It’s pretty neat when you try to assign multiple variables, compare below style:

a=1

b=2

c=3

d=4

verse this style:

a, b, c, d = 1,2,3,4