# A concise O(n) time, O(1) in place solution

• ``````// O(N) time, O(1) space in total

// find the middle node: O(n)
while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
}

// cut from the middle and reverse the second half: O(n)
p1->next = NULL;

while (p2) {
p1 = p2->next;
p2 = p1;
}

// merge two lists: O(n)
auto t = p1->next;
p1 = p1->next = p2;
p2 = t;
}

//    auto t = p1->next;
//    p1->next = p2;
//    p2 = p2->next;
//    p1 = p1->next->next = t;
//}
}``````

• My code is almost the same with yours except the "Merge Two Lists" part. Your code is much more efficient! So concise!

• good idea!how nice solution!

• what an elegant solution!!!!!!!!!!!!!!!

• Thank you for your good sharing. Smarter than mine.

• so concise, so brief

• 2 improvements needed to pass all test cases

1. If list contains only 2 nodes, check the condition at the top and return. There is no need to process further.

2. For lists that contain even no of nodes. For example 1->4->3->2. Your solution returns 1->4->3. For the solution to work for this case I made the following change.
ListNode *prev=NULL;
auto t = p1->next;
prev=p1;
p1 = p1->next = p2;
p2 = t;
}
if(p2)
{
prev->next=p2;
}

• @shichaotan your merging is cool...

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