Insert Greatest Common Divisors in Linked List

NeetCode: Insert Greatest Common Divisors in Linked List · LeetCode: 2807. Insert Greatest Common Divisors in Linked List · Difficulty: Medium

Given the head of a linked list of positive integers, insert between every two adjacent nodes a new node whose value is the greatest common divisor (GCD) of those two nodes. Return the head.

Example

Text

Input:  18 -> 6 -> 10 -> 3
Output: 18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3

Input:  7
Output: 7

The GCD comes from Euclid's algorithm: gcd(a, 0) = a and gcd(a, b) = gcd(b, a % b). The larger argument at least halves every two steps, so it takes O(log(min(a, b))) time.

The list uses the ListNode class from LeetCode: an int val and a next reference that is null at the end of the list. Java linked structures use null and mutable fields directly.

Brute force: copy to an ArrayList and rebuild

Read the values into an ArrayList, build a second list where a gcd is placed between each adjacent pair, and rebuild a linked list from it. This allocates a whole new list and copies every value.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            values.add(cur.val);
        }
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < values.size(); i++) {
            if (i > 0) {
                out.add(gcd(values.get(i - 1), values.get(i)));
            }
            out.add(values.get(i));
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : out) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

public class Main {
    // Helpers for the example: build a list from its values and read it back.
    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.insertGreatestCommonDivisors(fromArray(18, 6, 10, 3))));
        System.out.println(toList(s.insertGreatestCommonDivisors(fromArray(7))));
    }
}

Output

[18, 6, 6, 2, 10, 1, 3]
[7]

Time: O(n log V), where V is the largest value (the cost of the gcd calls). Space: O(n) for the copy and the new list.

Optimal: splice new nodes in place

Walk the list once. At a node cur with a successor nxt: create a node holding gcd(cur.val, nxt.val) that points to nxt, and hang it after cur. Then move cur to nxt, skipping over the inserted node. Only the n - 1 new nodes are allocated; the original nodes are reused.

Java

import java.util.ArrayList;
import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode nxt = cur.next;
            cur.next = new ListNode(gcd(cur.val, nxt.val), nxt);
            cur = nxt; // skip the inserted node
        }
        return head;
    }
}

public class Main {
    // Helpers for the example: build a list from its values and read it back.
    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) {
            out.add(cur.val);
        }
        return out;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(toList(s.insertGreatestCommonDivisors(fromArray(18, 6, 10, 3))));
        System.out.println(toList(s.insertGreatestCommonDivisors(fromArray(7))));
    }
}

Output

[18, 6, 6, 2, 10, 1, 3]
[7]

Time: O(n log V). Space: O(1) extra beyond the n - 1 nodes the answer must contain.