/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
int GCD(int num1, int num2)
{
if (num2 == 0)
return num1;
return GCD(num2, num1 % num2);
}
ListNode* insertGreatestCommonDivisors(ListNode* head)
{
ListNode* ptr = head;
while(ptr->next != nullptr)
{
int a = ptr->val;
int b = ptr->next->val;
int c = GCD(a, b);
/*** 1. Correct ***/
ListNode* n = new ListNode(c);
n->next = ptr->next;
ptr->next = n;
/*** 2. Wrong ***/
ListNode n(c, ptr->next);
ptr->next = &n;
ptr = ptr->next->next;
}
return head;
}
};
LyoqCiAqIERlZmluaXRpb24gZm9yIHNpbmdseS1saW5rZWQgbGlzdC4KICogc3RydWN0IExpc3ROb2RlIHsKICogICAgIGludCB2YWw7CiAqICAgICBMaXN0Tm9kZSAqbmV4dDsKICogICAgIExpc3ROb2RlKCkgOiB2YWwoMCksIG5leHQobnVsbHB0cikge30KICogICAgIExpc3ROb2RlKGludCB4KSA6IHZhbCh4KSwgbmV4dChudWxscHRyKSB7fQogKiAgICAgTGlzdE5vZGUoaW50IHgsIExpc3ROb2RlICpuZXh0KSA6IHZhbCh4KSwgbmV4dChuZXh0KSB7fQogKiB9OwogKi8KIApjbGFzcyBTb2x1dGlvbiB7CnB1YmxpYzoKICAgIGludCBHQ0QoaW50IG51bTEsIGludCBudW0yKQogICAgewogICAgICAgIGlmIChudW0yID09IDApCiAgICAgICAgICAgIHJldHVybiBudW0xOwogICAgICAgIHJldHVybiBHQ0QobnVtMiwgbnVtMSAlIG51bTIpOwogICAgfQoKICAgIExpc3ROb2RlKiBpbnNlcnRHcmVhdGVzdENvbW1vbkRpdmlzb3JzKExpc3ROb2RlKiBoZWFkKQogICAgewogICAgICAgIExpc3ROb2RlKiBwdHIgPSBoZWFkOwogICAgICAgIHdoaWxlKHB0ci0+bmV4dCAhPSBudWxscHRyKQogICAgICAgIHsKICAgICAgICAgICAgaW50IGEgPSBwdHItPnZhbDsKICAgICAgICAgICAgaW50IGIgPSBwdHItPm5leHQtPnZhbDsKICAgICAgICAgICAgaW50IGMgPSBHQ0QoYSwgYik7CiAgICAgICAgICAgIAogICAgICAgICAgICAvKioqIDEuIENvcnJlY3QgKioqLwogICAgICAgICAgICBMaXN0Tm9kZSogbiA9IG5ldyBMaXN0Tm9kZShjKTsKICAgICAgICAgICAgbi0+bmV4dCA9IHB0ci0+bmV4dDsKICAgICAgICAgICAgcHRyLT5uZXh0ID0gbjsKICAgICAgICAgICAgCiAgICAgICAgICAgIC8qKiogMi4gV3JvbmcgKioqLwogICAgICAgICAgICBMaXN0Tm9kZSBuKGMsIHB0ci0+bmV4dCk7CiAgICAgICAgICAgIHB0ci0+bmV4dCA9ICZuOwogICAgICAgICAgICAKICAgICAgICAgICAgcHRyID0gcHRyLT5uZXh0LT5uZXh0OwogICAgICAgIH0KICAgICAgICByZXR1cm4gaGVhZDsKICAgIH0KfTs=