[Leetcode] Reorder List

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:

1. Split into two list: L0→L1→... and ...→Ln-1→Ln

2. Reverse ...→Ln-1→Ln into Ln→Ln-1→...

3. Merge  L0→L1→... and Ln→Ln-1→... into one list

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

    ListNode* reverseNode(ListNode* head)
    {
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr != NULL)
        {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }


    void reorderList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return;
        //split
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = NULL;
        while(fast != NULL && fast->next != NULL)
        {
            prev = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        //reverse
        prev->next = NULL;
        ListNode* h2 = reverseNode(slow);
        
        //merge
        ListNode* h1= head;
        while(h1 != NULL && h2 != NULL)
        {
            ListNode* h1Next = h1->next;
            ListNode* h2Next = h2->next;
            h1->next = h2;
            if (h1Next != NULL)
            {
                h2->next = h1Next;
            }
            h1 = h1Next;
            h2 = h2Next;
        }
    }
};