[LeetCode] Reorder List

Problem Statement (link):

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Analysis:
If we are given an array, we simply need to interleave the corresponding nodes with O(1) access time. However, linked list doesn't offer us a constant access time and it's too costly to traverse the list every time to access a node.

If we think about how we construct the reordered list, we notice that we want to traverse from L_n to L_(n/2) reversely for insertion, where all the inserted nodes are from the second half of the list. If we could reverse the second half list, we could access each nodes in linear time.

Thus, we use the following algorithm:
1) Split the list into two halves. We find the middle of the list using two pointers - a slow pointer and a fast pointer. This costs us O(n) time.
2) Reverse the second half of the list. This takes O(n) time using the algorithm below.
3) Traverse the two lists one node each time and link pairs together --> O(n) time.

For step 2), it's easy to see that bubble sort would do the work with time O(n^2). But there is a faster way with O(n) time: From the start, we repeatedly insert the current node to the front until we reach the end, i.e.,

Original list:         a --> b --> c --> d
Insert a to front:   b --> a --> c --> d
Insert c to front:   c --> b --> a --> d
Insert d to front:  d --> c --> b --> a
Done.

The overall algorithm takes O(n) time.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    // time: O(N), space: O(1)
    void reorderList(ListNode *head) {
        if (head==NULL || head->next==NULL) return;
        // split list into two halves
        ListNode* slow=head; ListNode* fast=head;
        while(fast!=NULL && fast->next!=NULL) {
            slow=slow->next;
            fast=fast->next->next;
        }

        // Reverse the 2nd half list, slow is head of the 2nd half
        slow=rev(slow);

        // Add 2nd list interleaved to 1st list
        ListNode* cur=head; // don't move head
        ListNode* tmp1=cur->next; ListNode* tmp2=slow->next;

        while(slow!=NULL) {
            tmp1=cur->next; tmp2=slow->next;
            cur->next=slow;
            slow->next=tmp1;
            slow=tmp2;
            cur=tmp1;
        }
        if (tmp1!=NULL) tmp1->next=NULL;
    }

    ListNode* rev(ListNode *head) {
        if (head->next==NULL) return head;
        ListNode* prev=new ListNode(0);
        prev->next=head;
        head=prev;
        ListNode* cur=prev->next;

        while(cur->next!=NULL) {
            ListNode* tmp= cur->next;
            cur->next=tmp->next;
            tmp->next=prev->next;
            prev->next=tmp;
        }
        return prev->next;
    }
};