Simple C++ with O(n) time complexity and O(1) space


#1

Find the midway node in the list.
Reverse the list which starts at midway node.

Alter the original node by linearly walking the start of the original list and reversed list.
And return this altered list.

list*
midway(list *slow) {
if (!slow) return nullptr;
list *fast = slow->next;
if (!fast) return nullptr;

while(fast) {
    slow = slow->next;
    if (fast->next) {
        fast = fast->next->next;
    } else {
        fast = fast->next;
    }
}


return slow;

}

list *reverse(list *start) {

list *q = start;
list *p = start->next;
list *r = nullptr;

while(q) {
    q->next = r;
    r = q;
    q = p;
    p = p ? p->next : nullptr;
}


return r; // travsersable by r

}

list *
subtract(list *l) {
list *mid = midway(l);
if (!mid) return l; // nothing to do

list *start = l;
list *p = nullptr;
list *rev = reverse(mid);
list *q = rev;

while (start != mid) {
    start->v = rev->v - start->v;
    p = start;
    start = start->next;
    rev = rev->next;
}

list *r = q;
p->next = reverse(q);
r->next = nullptr;
return l;

}