2807. Insert Greatest Common Divisors in Linked List LeetCode Solution

In this guide, you will get 2807. Insert Greatest Common Divisors in Linked List LeetCode Solution with the best time and space complexity. The solution to Insert Greatest Common Divisors in Linked List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Insert Greatest Common Divisors in Linked List solution in C++
4. Insert Greatest Common Divisors in Linked List solution in Java
5. Insert Greatest Common Divisors in Linked List solution in Python
6. Additional Resources

Problem Statement of Insert Greatest Common Divisors in Linked List

Given the head of a linked list head, in which each node contains an integer value.
Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.
Return the linked list after insertion.
The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Example 1:

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
– We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes.
– We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
– We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.

Example 2:

Input: head = [7]
Output: [7]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.

Constraints:

The number of nodes in the list is in the range [1, 5000].
1 <= Node.val <= 1000

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

2807. Insert Greatest Common Divisors in Linked List LeetCode Solution in C++

class Solution {
 public:
  ListNode* insertGreatestCommonDivisors(ListNode* head) {
    for (ListNode* curr = head; curr->next != nullptr;) {
      ListNode* inserted =
          new ListNode(__gcd(curr->val, curr->next->val), curr->next);
      curr->next = inserted;
      curr = inserted->next;
    }
    return head;
  }
};
/* code provided by PROGIEZ */

2807. Insert Greatest Common Divisors in Linked List LeetCode Solution in Java

class Solution {
  public ListNode insertGreatestCommonDivisors(ListNode head) {
    for (ListNode curr = head; curr.next != null;) {
      ListNode inserted = new ListNode(gcd(curr.val, curr.next.val), curr.next);
      curr.next = inserted;
      curr = inserted.next;
    }
    return head;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
// code provided by PROGIEZ

2807. Insert Greatest Common Divisors in Linked List LeetCode Solution in Python

class Solution:
  def insertGreatestCommonDivisors(
      self, head: ListNode | None
  ) -> ListNode | None:
    curr = head
    while curr.next:
      inserted = ListNode(math.gcd(curr.val, curr.next.val), curr.next)
      curr.next = inserted
      curr = inserted.next
    return head
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.