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

题意：

• 输入一个单链表，将该单链表奇数节点放在前半部分，偶数节点放在后半部分，不改变奇数节点和偶数节点之间的相对顺序，返回新的链表。

方法一：

解题思路：

• 一次遍历，奇数的节点组成一个链表，偶数的节点组成一个链表，然后将链表合并即可。
• oddHead,oddTail记录奇数节点链表的头尾节点;evenHead,evenTail记录偶数节点链表的头尾节点；遍历时更新oddTail,evenTail；合并时将evenHead接在oddTail之后。

图解如下：

代码如下：

/**
 * 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) {
        // write code here
        if(head==nullptr||head->next==nullptr)
            return head;
        //分别表示奇数位节点组成的链表头尾节点，以及偶数位节点组成的链表头尾节点。
        ListNode *oddHead=head,*evenHead=head->next;
        ListNode *oddTail=head,*evenTail=evenHead;
        //p是遍历的临时节点
        ListNode* p=head->next->next;
        while(true){
            //p不存在则退出循环
            if(!p)
                break;
            //奇数位节点
            oddTail->next=p;
            p=p->next;
            oddTail=oddTail->next;
            if(!p)
                break;
            //偶数位节点
            evenTail->next=p;
            p=p->next;
            evenTail=evenTail->next;
        }
        //连接两个链表
        oddTail->next=evenHead;
        evenTail->next=nullptr;
        return oddHead;
    }
};

复杂度分析：

时间复杂度：，遍历一次。
空间复杂度：，常数个临时变量。