Given last node of singly linked list, how do we find head node

Question

Given last node of singly linked list, how do we find head node?

Let's say given JSON:

{ "id": "A", "next": "B" }, { "id": "B", "next": "C" } { "id": "C", "next": "D" } { "id": "D", "next": null }

Now assume that above is not sorted and we need to figure out HEAD element 'A'.

Answer 1

You can use Array.prototype.find to find an element that's id is not the value next of another object in the list. Assuming a valid non-empty singly-linked list there must be exactly one element which satisfies that condition (the head). If the list is empty head will be assigned the value undefined.

const json = '[{"id": "A", "next": "B"}, {"id": "B", "next": "C"},{"id": "C", "next": "D"},{"id": "D", "next": null}]';
const objects = JSON.parse(json);

const head = objects.find( a => ! objects.find( b => a.id === b.next ) );

console.log( head );