class Solution {
public:
void reorderList(ListNode *head) {
if(head){
int len = 0;
ListNode* tmp = head;
while(tmp){
len++;
tmp = tmp>next;
}
len = len/2;
tmp = head;
while(len) tmp = tmp>next; //tmp point to the mid node;
ListNode* head2 = tmp>next;
tmp>next = NULL;
head2 = reverseList(head2);
head = mergeLinkedList(head, head2);
}
}
//reverse a linked list.
ListNode* reverseList(ListNode* head) {
if(head == NULL  head>next == NULL) return head;
ListNode *pre = head, *cur = head>next, *next;
pre>next = NULL;
while(cur){
next = cur>next; //save the next node;
cur>next = pre;
pre = cur;
cur = next;
}
return pre;
}
//merge link list h1 and h2;
ListNode* mergeLinkedList(ListNode* h1, ListNode* h2)
{
if(!h1) return h2;
if(!h2) return h1;
ListNode* tmp1 = h1>next, *tmp2 = h2, *h = h1, *tmp = h;
int i = 1;
while(tmp1 && tmp2){
if(i%2 == 0){
tmp>next = tmp1;
tmp1 = tmp1>next;
}
else{
tmp>next = tmp2;
tmp2 = tmp2>next;
}
tmp = tmp>next;
i = (i+1) % 2;
}
if(tmp1) tmp>next = tmp1;
else if(tmp2) tmp>next = tmp2;
else tmp>next = NULL;
return h;
}
};
Reorder in O(n), but code seems a little redundancy


One redundancy I see is in the way to get the middle node.
For finding the mid node, you can reduce on extra pass by taking two pointers, and incrementing one pointer at the speed of one node at a time, and the other one at double the speed. When the latter reaches null, guess where the first pointer would be?

I am using the similar idea. For the method mergeLinkedList, it can be cleaner, like this:
ListNode *appendNode(ListNode* tail, ListNode *node) { tail>next = node; return tail>next; } ListNode *merge(ListNode *head1, ListNode *head2) { ListNode *head = head1; head1 = head1>next; ListNode * tail = head; while (head1 != nullptr) { tail = appendNode(tail, head2); head2 = head2>next; tail = appendNode(tail, head1); head1 = head1>next; } appendNode(tail, head2); return head; }
Is it better?