一、题目
二、思路
时间复杂度O(n)即遍历一遍链表，奇偶指针odd循环链表，奇数指针不断串连奇数节点，偶数指针even不断串连偶数节点，最后奇数指针的结尾连接偶数节点的开始。
根据偶数指针进行while条件判断，注意为了确定本轮次的奇数链表存在下一个新节点，所以在while判断还要加上even->next != NULL。
while(even != NULL && even->next != NULL){ odd->next = even->next; odd = odd->next; even->next = odd->next; even = even->next; }
第一轮循环后：
三、C++代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* oddEvenList(ListNode* head) { if(head == NULL){ return head; } //偶数第一个节点 ListNode* evenhead = head->next; ListNode* odd = head; ListNode* even = head->next; 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; } };
