Check if sorted
Look ahead to curr.next to compare adjacent nodes without running off the end. About 9 minutes.
Looking ahead one step
In an array, you can compare a value with the one right after it by index. A linked list has no index math. Instead, when you are standing on the current node, the node immediately after it is its next pointer.
So you can compare the current value with the next node's value directly, like checking whether the person ahead of you in a queue is shorter.
The pointer is on 2, and the next node holds 5. 2 is at most 5, so the order holds. Advance.
Guarding the last node
When you stand on the last node, its next pointer is null, and trying to read a value from null is a crash. To safely compare every adjacent pair, make the loop condition require both the current node and the node after it.
The loop then stops as soon as you reach the last node.
curr = head
while curr and curr.next:
if curr.val > curr.next.val:
return False
curr = curr.next
return TrueWhy does the loop check curr.next != null instead of curr != null?
- ABecause on the last node, reading curr.next.val would crash
- BTo make the loop run twice as fast
- CBecause linked lists can only be read backward
Show the answer
Because on the last node, reading curr.next.val would crash. On the last node, curr.next is null, so accessing curr.next.val would throw a null pointer exception.
Check if sorted
Given the head of a linked list, return true if the list is sorted in non-decreasing order (for every node, its value is less than or equal to the next node's value). Otherwise, return false. An empty list or a list with only one node is sorted.
head = [1, 2, 4, 7] → true
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000