Teaching Kids Programming – Algorithms to Check if Linked List Strictly Increasing

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the head of a singly linked list head, return whether the values of the nodes are sorted in a strictly increasing order.

Constraints
1 ≤ n ≤ 100,000 where n is the number of nodes in head
Example 1
Input
head = [1, 5, 9, 9]
Output
False
Explanation
Even though this list is sorted, it’s not strictly increasing since 9 is repeated.

Example 2
Input
head = [1, 5, 8, 9]
Output
True
Explanation
The values 1, 5, 8, 9 are strictly increasing.

Algorithms to Check a Strictly Increasing Linked List

We can first convert the linked list to list and then we can easily check if that list is strictly increasing by checking two adjacent numbers:

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, head):
        data = []
        while head:
            data += [head.val]
            head = head.next
        for i in range(1, len(data)):
            if data[i] <= data[i - 1]:
                return False
        return True

Need to walk through the list twice and hence O(N) time complexity. The space complexity is O(N) as we are allocating space to store the elements in the linked list.

We don’t need to convert linked list to list – we can just compare the adjacent Linked List Nodes:

Current and Next:

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, head):
        """
        while head.next:
            if head.val >= head.next.val:
                return False
            head = head.next
        return True

Other similar implementations but different labeling of the nodes:

Fast and Slow Pointer:

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, head):
        slow = head
        fast = head.next
        while fast:
            if slow.val >= fast.val:
                return False
            slow = slow.next # or slow = fast
            fast = fast.next
        return True

Current and Previous Node:

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, head):
        if not head or not head.next:
            return True
        prev = head
        head = head.next
        while head:
            if head.val <= prev.val:
                return False
            prev = head
            head = head.next
        return True

All these three approaches O(N) time (iterate the Linked List once) and space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —