链表奇偶重排

图解：

链接

思路：

1.判断一下链表是否为空，如果链表为空，就不需要进行奇偶重排

2.否则就odd（奇数位）=head,even（偶数位）=head.next,evenHead（偶数链表的头结点）=head.next;

3.只要even和even还没有指向null,那么就继续

4.每次将odd指向奇数位，将even指向偶数位

5.最后将偶链表连接到奇链表的后面

代码：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        //判断一下如果链表是不是空的
        //如果链表是空的，就不需要进行奇偶重排，直接返回null
         if(head==NULL){
             return head;
         }
         //否则让odd指向链表的头结点
         //even指向链表的第二个节点
         //记录一下偶链表的头节点，方便后序将偶链表连在奇链表的后面
         ListNode *odd=head;
         ListNode *even=head->next;
         ListNode *evenHead=even;
         //由于每次是跨越两个节点，且even节点是在后面的，所以判断一下，如果发现even或even的后一个节点指向null,那么就结束
         while(even!=NULL&&even->next!=NULL){
            //将奇数位的相连，偶数位的相连
             odd->next=even->next;
             odd=odd->next;
             even->next=odd->next;
             even=even->next;
         }
         //最后再将偶数表连在奇数表的后面
         odd->next=evenHead;
         return head;
    }
};