问题描述

    给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
数据范围：节点数量满足 0≤n≤105，节点中的值都满足 0≤val≤1000
要求：空间复杂度 O(n)，时间复杂度O(n)
如果按照题目要求的空间复杂度为O(n),那么很简单，只需要重新建一个尾插的单链表放偶数
位的节点。假设原链表只存奇数位的节点，然后遍历结束后，原链表尾部最后接上新建链表
的头部就可以了。
那么我们可不可以想办法让空间复杂度变为O(1)呢？
我们只需要定义两个指针odd(奇数位指针)，even(偶数位指针)。奇数位开始指向头节点，偶数
位指针开始指向头节点的下一个节点。然后只要even!=null&&even->next!=null，就做如下操作：
odd->next=even->next, odd=odd->next; even->next=odd->next,even=even->next;
在循环体内不用担心指针会越界，因为循环判断条件已经限定了当even=null或even->next=null
以1->2->3->4->5->null和1->2->3->4->5->6->null为例
第一次：odd 1->3->4->5->null，ood指向3，1-> 3->4->5->6->null;odd指向3
               even 2->4->5->null， even指向4，2->4->5->6->null;    even指向4
第二次：odd 1->3->5->null，     odd指向5，1->3->5->6->null;      odd指向5
              even 2->4->null，    evec指向null， 2->4->6->null;        evec指向6
当链表长度为奇数时，是以veve==null退出循环，此时odd指针指向的是5，只需要odd->next指向
even的头节点。
当链表长度为偶数时，是以even->next==null退出循环，此时odd指针指向5，也只需要odd->next
指向even的头节点。
那么又会出现一个新问题，even的头结点在哪儿，只需要开始的时候定义一个指针ehead指向head->next，
这样ehead就是even的头节点。
最后让odd->next=ehead就行了。
复杂度分析：
时间复杂度：O(n)，只需要(n-1)/2次就结束循环了。
空间复杂度O(1)，常数个变量，且没有额外申请空间。 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        ListNode *odd,*even,*ehead;
        odd=head,even=head->next;
        ehead=even;
        while(even!=NULL&&even->next!=NULL){
            odd->next=even->next;
            odd=odd->next;
            even->next=odd->next;
            even=even->next;
        }
        odd->next=ehead;
        return head;
    }
};