Insert Greatest Common Divisors in Linked List

MediumLinked Listmath

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given the head of a linked list of positive integers. Between **every pair of adjacent nodes**, insert a new node whose value is the **greatest common divisor** of those two neighbors' values. Only pairs from the original list get a new node; the inserted nodes do not create further insertions. Return the head of the resulting list. A list of n nodes becomes 2n - 1 nodes.

Examples

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
gcd(18, 6) = 6, gcd(6, 10) = 2, gcd(10, 3) = 1.
Input: head = [7]
Output: [7]
A single node has no adjacent pairs, so the list is unchanged.

Constraints

  • The number of nodes is in `[1, 5000]`.
  • `1 <= Node.val <= 1000`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More math problems