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}.
典型的なチェーンテーブルの操作の基本功のテーマを考察して、チェーンテーブルの操作に対して2つの最も基本的なにほかならない:挿入と削除、ここでは与えられた方式に従って、チェーンテーブルを並べ替えることを要求して、並べ替えの後で、LnはLn-1の前に並ぶため、しかし与えられたノードのデータ構造の中で現在のノードの前駆ノードのポインタを保存していないで、同時にアルゴリズムは投機が巧みにノードの値を変えることを許さない.
最も一般的な思想:毎回Lnを探しに行くなら...Ln-1...の位置はテーマの要求の操作を実行して、それでは毎回前に挿入するノードを探し当ててO(n)を必要として、全部でO(n)回を挿入する必要があって、時間の複雑度はO(n 2)、空間の複雑なO(1);
さらに考えると(私の解法):実装しましょうすべてのノードのアドレスをポインタ配列pointers[n]として保存すれば、操作中に配列中のノードを操作するだけでいいので、「Ln」ノードを検索するたびに時間を省くことができ、これによって時間複雑度O(n)、空間複雑度O(n);
さらに(このことは他人の):Discussプレートでは,後半のチェーンテーブルを逆順操作し,分解された2つの部分を統合すればよいアルゴリズムが与えられ,時間複雑度O(n),空間複雑度O(1):
私の解法:

/**
 * 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 ;
        }
        //  ：
        //               ，            
        //          
        //        
        ListNode *ptop=head;
        ListNode *pbuttom=head;
        ListNode **pPointerArray;
        int  arraySize=0;
        while (pbuttom!=NULL)
        {
            pbuttom=pbuttom->next;
            arraySize++;
        }

        pPointerArray=new ListNode*[arraySize];
        pbuttom=head;
        int i=0;
        while (pbuttom!=NULL)
        {
            pPointerArray[i]=pbuttom;
            i++;
            pbuttom=pbuttom->next;
        }
        
        i=0;
        int j=arraySize-1;
        while (i<j)
        {
            //cut j
            pPointerArray[j-1]->next=pPointerArray[j]->next;
            //insert  j to i next
            pPointerArray[j]->next=pPointerArray[i]->next;
            pPointerArray[i]->next=pPointerArray[j];
            i++;
            j--;
        }
        
        delete[] pPointerArray;
    }
};

最良の解法:

/**
 * 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 ;
    //    }
    //    //  ：
    //    //               ，            
    //    //          
    //    //        
    //    ListNode *ptop=head;
    //    ListNode *pbuttom=head;
    //    ListNode **pPointerArray;
    //    int  arraySize=0;
    //    while (pbuttom!=NULL)
    //    {
    //        pbuttom=pbuttom->next;
    //        arraySize++;
    //    }

    //    pPointerArray=new ListNode*[arraySize];
    //    pbuttom=head;
    //    int i=0;
    //    while (pbuttom!=NULL)
    //    {
    //        pPointerArray[i]=pbuttom;
    //        i++;
    //        pbuttom=pbuttom->next;
    //    }
    //    
    //    i=0;
    //    int j=arraySize-1;
    //    while (i<j)
    //    {
    //        //cut j
    //        pPointerArray[j-1]->next=pPointerArray[j]->next;
    //        //insert  j to i next
    //        pPointerArray[j]->next=pPointerArray[i]->next;
    //        pPointerArray[i]->next=pPointerArray[j];
    //        i++;
    //        j--;
    //    }
    //    
    //    delete[] pPointerArray;
    //}
    void reorderList(ListNode *head) {
        if (head==NULL)
        {
            return ;
        }

        //calculate the length of the list
        ListNode *pCurrent=head;
        int ListLen=0;
        while (pCurrent!=NULL)
        {
            ListLen++;
            pCurrent=pCurrent->next;
        }
        if (ListLen==1)
        {
            return;
        }
        //partation
        int halpLen=ListLen-ListLen/2;
        ListNode *pSecond=head;
        ListNode *pPreSecond=NULL;
        for (int i=0;i<halpLen;i++)
        {
            pPreSecond=pSecond;
            pSecond=pSecond->next;
        }
        pPreSecond->next=NULL;

        //reverse Second half
        pPreSecond=pSecond;
        pSecond=pSecond->next;
        pPreSecond->next=NULL;
        ListNode *pPostSecond;
        while (pSecond!=NULL)
        {
            //            
            pPostSecond=pSecond->next;
            //          
            pSecond->next=pPreSecond;
            //        
            pPreSecond=pSecond;
            //  pSecond        
            pSecond=pPostSecond;
        }
        pSecond=pPreSecond;

        ListNode *pFirst=head;
        while (pSecond!=NULL)
        {
            //            
            pPostSecond=pSecond->next;
            //         
            pSecond->next=pFirst->next;
            pFirst->next=pSecond;

            //         
            pFirst=pSecond->next;
            pSecond=pPostSecond;
        } 
    }
};