# Sharing my O(n) time and O(1) space c++ solution and O(n) space solution

• reverse the half of the linked list and compare one by one can do this in o(n) time and o(1) space.
But doing this will change the input (well, you can reverse the 2nd half back to keep it original)

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:

while(fast&&fast->next){
fast=fast->next->next;
preSlow=slow;
slow=slow->next;
}
preSlow->next=NULL;
while(y){
z=y->next;
y->next=x;
x=y;
y=z;
}

while(head){    // first half of the list node always has equal or less than 1 item than 2nd half,
// so use head not x to check when finished
x=x->next;
}
return true;
}
};
``````

This simple solution uses queue and stack, and doesn't change the input, but use O(n) space

``````   /**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
stack<int> st;
queue<int> q;