328.Odd Even Linked List


328.Odd Even Linked List My Submissions
Question
Total Acceepted: 9271 
Total Submissions: 24242497 
Difficulty: Easy
Gven a singly linked list、group all odd nodes together followed by the even nodes.Please note here we are talking about the node number and not the value in the nodes.
You shoud try to do it in place.The program shuld run in O(1)space complexity and O(nodes)time complexity.
Example:Given  1->2->3->4->5->NULL、リセット  1->3->5->2->4->NULL.
Note:The relative order inside both the even and odd groups shoud remail as it was in the input.  The first node is consided odd、the second node even and so on…
Crediits:Special thanks to @aadarsh jajodia for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
Show Tags
分析:
単純模擬思想、
二つのポインタを申請します.一つは常に現在接続を確立する奇数ノード、一つは偶数…最後に奇数チェーンと偶数チェーンを連結すればいいです.
明らかに、まず奇数のポインタを作って、偶数のポインタを返します.
奇数のポインタを作るときは、偶数のポインタの次の位置が存在するかどうかを見て、接続を確立します.
奇数ポインタを現在の奇数ノードに移動します.
存在しない場合は偶数チェーンと奇数チェーンの最終的な連結が完了します.
偶数のポインタは同じです.
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || head->next==NULL || head->next->next==NULL)
            return head;
        ListNode* oddNode=head;//  
        ListNode* evenNode=head->next;//  
        ListNode* evenhead=head->next;//   
        while(true)
        {
            if(evenNode->next!=NULL)//         
             {   
                 oddNode->next=evenNode->next;
                 oddNode=evenNode->next;//    
             }else
             {
                 oddNode->next=evenhead;
                 evenNode->next=NULL;
                 break;//                  
             }
             
             if(oddNode->next!=NULL)
             {   
                 evenNode->next=oddNode->next;
                 evenNode=oddNode->next;
             }else
             {
                 oddNode->next=evenhead;
                 evenNode->next=NULL;
                 break;//  ......      
             }   
        }
        return head;
    }
};
簡略コード:
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || head->next==NULL || head->next->next==NULL)
            return head;
        ListNode* oddNode=head;//  
        ListNode* evenNode=head->next;//  
        ListNode* evenhead=head->next;//   
        while(evenNode!=NULL && evenNode->next !=NULL)//                           
        {
             oddNode->next=evenNode->next;
             oddNode=evenNode->next;//    
             evenNode->next=oddNode->next;
             evenNode=oddNode->next;
        }
        oddNode->next=evenhead;
        return head;
    }
};
注:このブログはEbowTangのオリジナルです.その後も引き続き本文を更新します.転載する場合は、必ず本条情報をコピーしてください.
原文の住所:http://blog.csdn.net/ebowtang/article/details/50611707
作者のブログ:http://blog.csdn.net/ebowtang