Insert Greatest Common Divisors in Linked List

Insert Greatest Common Divisors in Linked List is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.

Problem statement

You are given head, the first node of a singly linked list. Each node stores a positive integer, and the list is ordered from the head node toward the final node.

For every pair of adjacent nodes, calculate their greatest common divisor (GCD): the largest positive integer that divides both node values. Insert a new node containing that GCD between the two adjacent nodes.

Keep every original node in its original order, and return the head of the modified list. If head is null, return null.

Example 1:

Input: head = [14,25,9] Output: [14,1,25,1,9] Explanation: The GCDs of the adjacent pairs are 1 and 1, so those values are inserted between the original nodes.

Example 2:

Input: head = [18,30] Output: [18,6,30] Explanation: The only adjacent pair has GCD 6, which is placed between the two nodes.

Example 3:

Input: head = [8,12,20] Output: [8,4,12,4,20] Explanation: The adjacent GCDs are gcd(8,12) = 4 and gcd(12,20) = 4.

Constraints:

- 0 <= number of nodes in head <= 10^5 - 1 <= value in each node <= 1000 - head is either null or the first node of a singly linked list - Each node has at most one next node

Topics and companies

Topics: Linked List, Math, Number Theory, Pointers.

How to practise Insert Greatest Common Divisors in Linked List on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log V), where n is the number of original nodes and V is the maximum node value. time and O(n) for the inserted nodes, with O(1) auxiliary space. space.

Open Insert Greatest Common Divisors in Linked List in the code editor, or read the Insert Greatest Common Divisors in Linked List editorial for a worked solution with its approach and complexity analysis.

Where Insert Greatest Common Divisors in Linked List sits in the DSA pattern sheet

Problems related to Insert Greatest Common Divisors in Linked List

Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:

Preparing this workspace.