Leetcode Grind Day 1

It’s time to grind ladies and gentleman. I’m starting out with an easy leetcode problem today. Going to work my way up to harder problems as the days go on.

Today’s problem, finding the middle of singly linked list.

Singly Linked List⌗

This data structure is a unidirectional form of the linked list. It can only be traversed from one direction (head to tail nodes).

Each node in the list has two pointers. One for it’s value representation, and another pointer for the next node in the list. In the example above, the head node is 1. It’s next node value points to the 2 Node. The tail node is 4, and it’s next node is NULL, indicating it’s the end of the list.

Problem Statement⌗

Given a singly linked list, we must return the middle node. If there are two middle nodes, then we must return the second middle node. In the diagram above, the middle node would be 3. The leetcode problem statement says we must return a slice of the list that contains the middle node, all the way up to the last node. Let’s talk about our approach to this problem.

My first thought is to take the value of the tail and divide it by two. I’m going to cast it as an int to round the number to a whole number. Using the diagram above

>>> int(4/2)
2

The result of the division corresponds with the index of the middle node in the list. In this case node 3 is at the 2nd index value. Then using string slicing in python, we can return a list that has the middle node as the head, and the tail at the end of the list:

return head[2:]

The full code solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        index = int(head[-1].val / 2) # round whole number in case the tail is odd
        return head[index:]  # returns [3,4]

My initial thought failed miserably. This is why I need to practice Leetcode.

You cannot index the ListNode object List as if it were a traditional python list. I need to come up with something else. In order to traverse the Linked List, you need to call the next method on the nodes.

Day 1 for me is not off to a good start. I had to do some some googling and reading leetcode discussions. A good solution came across my feed. It’s utilizing two pointers: one to keep track of the current node in the traversal, and another node that traverses the list twice as fast.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = fast = head
        while fast and fast.next:
            curr = curr.next
            fast = curr.next.next
        return curr

The solution is simple, and I was overthinking things. Calling next twice for the fast pointer made it easy to keep track of the future nodes. The while condition keeps track of the fast pointer, as well as the fast pointer’s next node to ensure when the tail is reached, the traversal stops.

Using the example linked list diagram above, lets review the iterations:

(Start of Program)

Iteration One

Iteration Two

At the 2nd iteration, the while loop’s condition will be met and the curr pointer will be returned. In this case the solution will return [3,4], as expected.