LeetCode刷题（C++）——Odd Even Linked List（Medium）

水深无声 2022-06-15 01:09 207阅读 0赞

**Given 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 should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.**

**Example:  
Given `1->2->3->4->5->NULL`,  
return `1->3->5->2->4->NULL`.**

**Note:  
The relative order inside both the even and odd groups should remain as it was in the input.**

**The first node is considered odd, the second node even and so on ...**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* oddEvenList(ListNode* head) {
            if(head==NULL){
                return NULL;
            }
            ListNode* head1=NULL,*tail1=NULL,*head2=NULL,*tail2=NULL;
            for(int i=1;head;++i,head=head->next){
                if(i & 1){
                    if(tail1){
                        tail1=tail1->next=head;
                    }
                    else{
                        head1=tail1=head;
                    }
                }
                else if(tail2){
                    tail2=tail2->next=head;
                }
                else{
                    head2=tail2=head;
                }
            }
            if(tail1){
                tail1->next=head2;
            }
            else{
                head1=head2;
            }
            if(tail2){
                tail2->next=NULL;
            }
            return head1;
        }
    };