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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # 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 |
# 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 TrueNeed 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:
1 2 3 4 5 6 7 8 9 10 11 12 | # 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 |
# 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 TrueOther similar implementations but different labeling of the nodes:
Fast and Slow Pointer:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | # 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 |
# 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 TrueCurrent and Previous Node:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | # 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 |
# 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 TrueAll these three approaches O(N) time (iterate the Linked List once) and space complexity is O(1) constant.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Insertion Sort in Python (Simple Sorting Algorithm)
Next Post: Javascript Function to Update the Query String Value of a URL String
