📟作者主页：慢热的陕西人

🌴专栏链接：力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏，🍉留言

牛客热题：链表的奇偶重排

题目链接

链表的奇偶重排_牛客题霸_牛客网 (nowcoder.com)

方法一：额外辅助数组

思路

• 借助额外的两个数组
• 一个存奇数位，一个存储偶数位
• 将奇数位的数组先放入链表后，再将偶数位的数组放入链表

代码

    ListNode* oddEvenList(ListNode* head) {vector<int> v1;vector<int> v2;ListNode* cur = head;int i = 1;while(cur != nullptr){if(i % 2) v1.push_back(cur->val);else v2.push_back(cur->val);i++;cur = cur->next;}cur = head;for(auto vv : v1){cur->val = vv;cur = cur->next;}for(auto vv : v2){cur->val = vv;cur = cur->next;}return head;}

复杂度

时间复杂度：O(N), 遍历两次链表，一次取数字，一次放数字

空间复杂度：O(N), 借用了两个额外的数组空间，总长度为链表的长度

方法二：双指针

思路

• 我们使用双指针的思路，一个指针odd用于遍历奇数节点，一个指针even用于遍历偶数节点
• 首先我们将偶数节点都串连起来，奇数节点也串连起来。
• 将奇数节点尾部和偶数起始节点连接起来即可

代码

    ListNode* oddEvenList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* odd = head;ListNode* even = head->next;ListNode* evenBegin = even;while(even != nullptr && even->next != nullptr){odd->next = even->next;odd = odd->next;even->next = odd->next;even = even->next;}odd->next = evenBegin;return head;}

复杂度

时间复杂度：O(N),只遍历了一次链表

空间复杂度：O(1), 使用了常数个额外的变量