题解 | #链表的奇偶重排#

方法一：把奇数点和偶数点的结点分别连接在两个新建立的头结点，最后在把偶数点的头节点与奇数点的最后一个结点相连
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        if(head==NULL)
        {
            return NULL;
        }
        ListNode*p1=new ListNode(0);//奇结点的头链表
        ListNode*p2=new ListNode(0);//偶节点的头链表
        ListNode* p1_new=p1;
        ListNode* p2_new=p2;
        ListNode* p0=head;
        int n=1;
        while(p0!=NULL)
        {
         if(n%2!=0)//判断是否为奇数点
         {
            p1_new->next=p0;
            p1_new=p1_new->next;
        }
        else {
            p2_new->next=p0;
            p2_new=p2_new->next;
        }
        p0=p0->next;
        n++;
        }
        p2_new->next=NULL;
    p1_new->next=p2->next;

    return p1->next;
    }
};
方法二：采用双指针
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        if(head==NULL)
        {
            return NULL;
        }
        ListNode* p1_new=head;//奇数点的指针
        ListNode* p2_new=head->next;//偶数点的指针
        ListNode* p0=p2_new;
        while(p2_new->next!=NULL&&p2_new!=NULL)
        {
          p1_new->next=p2_new->next;
          p1_new=p1_new->next;
          p2_new->next=p1_new->next;
          p2_new=p2_new->next;
        }
        p1_new->next=p0;
        return head;
    }
};