Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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}.

The algorithm is straightforward.

First, divide the linked list into two parts equally. (left part may be longer than right part by one node)

Second, reverse the right part list.

Third, link the two parts craftily.

//What if the list is empty?
//What if the list contains odd elements?
//What time complexity?
//space complexity o(1)

//1. split the list into two parts
//2. reverse the right part list
//3. link them together
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        //extreme cases
        if(head == NULL) return ;
        
        //ordinary cases
        //1. find the mid of the list
        ListNode * fast, * slow;
        fast = slow = head;
        while(fast->next != NULL && fast->next->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode * leftStart = head;
        ListNode * rightStart = slow->next; // rightStart may be NULL
        slow->next = NULL;
        rightStart = reverse(rightStart);
        //list left may be longer than right by one node
        while(rightStart != NULL){
            ListNode * leftNext = leftStart->next;
            ListNode * rightNext = rightStart->next;
            leftStart->next = rightStart;
            rightStart->next = leftNext;
            leftStart = leftNext;
            rightStart = rightNext;
        }
        
        
        
    }
    //o(n), reverse linked list
    ListNode * reverse(ListNode * head){
        if(head == NULL) return NULL;
        ListNode * prev, * cur, * next;
        prev = NULL;
        cur = head;
        while(cur != NULL){
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
};