Second Last and Uniqueness | Dataford Interview Questions

HR Cloud processes ordered employee records using a singly linked list. Given the head of this list, return the value of the second-last node without modifying the list.

Your solution must traverse the list only once and use constant extra space. If the list contains fewer than two nodes, return None.

Formal Specification

Implement second_last(head), where head is either None or a nested dictionary representing a node:

Each node has an integer value field.
Each node has a next field containing another node or None.
Return the integer value stored in the node immediately before the final node, or None when fewer than two nodes exist.

Do not convert the list to an array, count its length in a separate traversal, or mutate any node.

Constraints

0 <= number of nodes <= 10^7
-10^9 <= node.value <= 10^9
The list is singly linked and acyclic
The input list must not be modified
Only one traversal is allowed
Extra space must be O(1)

Function Signature

def second_last(head):

Your question is Second Last and Uniqueness. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem