[LeetCode] Reorder List

Link : http://oj.leetcode.com/problems/reorder-list/

Analysis :
Two pointers, head and tail

head pointer : scans from the start
tail pointer  : first dig into the list until and last one. From there tail behaves as the node pointer pointing to the last node

head and tail scan from two ends and modify the link list as expected.
Be careful of the stop case.

 
/**
* 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) {
        if(head==NULL)
            return;
        int n=0;
        ListNode dummy(0);
        dummy.next = head;
        ListNode * cursor = &dummy;
        reorder(cursor, cursor);
    }
    
    bool reorder(ListNode*& head, ListNode* tail)
    {
        // base case
        if(tail->next==NULL)
            return true;
        // tail point to second to last node
        
        // stop case
        if(!reorder(head, tail->next)||head==tail||head->next==tail);
            return false;
        ListNode* tmp = tail->next;
        tail->next=NULL;
        
        tmp->next = head->next;
        head->next = tmp;
        
        head = head->next->next;
        return true;
    }
};