# Sharing my O(n) solution in c++, AC-2015.04.29

• class Solution
{

public:
return ;
}

``````    ListNode *pfast = head->next, *pslow = head;
while (pfast) {
pfast = (pfast->next) ? pfast->next->next : nullptr;
pslow = pslow->next;
}

ListNode *pbeg1 = head, *pbeg2 = reverseList(pslow->next);
pslow->next = nullptr;

}
``````

private:
}

``````    ListNode *pret = nullptr, *p = head, *pNext = head;
while (p) {
pNext = p->next;

p->next = pret;
pret = p;
p = pNext;
}

return pret;
}

ListNode *mergeTwoList(ListNode *ph1, ListNode *ph2) {
if (nullptr == ph1 && nullptr == ph2) {
return nullptr;
}

if (nullptr == ph1) {
return ph2;
}
if (nullptr == ph2) {
return ph1;
}

ListNode *pret = new ListNode(-1), *p = pret;
ListNode *p1 = ph1, *p2 = ph2;
bool is_p1 = true;
while (p1 && p2) {
if (is_p1) {
p->next = p1;
p1 = p1->next;
is_p1 = false;
} else {
p->next = p2;
p2 = p2->next;
is_p1 = true;
}

p = p->next;
}

p->next = nullptr;
p->next = (p1) ? p1 : p->next;
p->next = (p2) ? p2 : p->next;

return pret->next;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.