日野弥生：勉強しよう
LeetCode 328 - 奇偶链表
发表于2025年01月21日
本题的关键在于想到把非第0位的奇数位在原位删除，并在指定位置上添加。这就要求慢指针指向插入位置的前一位，而快指针指向被选中的奇数位。
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
/* 由于快指针跳一位遍历，所以必须排除掉头指针的边界条件 */
if(!head || !head->next)
return head;
ListNode *slow = head, *fast = head;
while(fast && fast->next)
{
/* 需要记录快指针的上一位以及慢指针的下一位，即偶数链条的头和尾 */
ListNode *fastPrev = fast->next, *slowNext = slow->next;
fast = fast->next->next;
/* 上一步跳两步，快指针可能为空 */
if(fast)
{
slow->next = fast;
fastPrev->next = fast->next;
fast->next = slowNext;
}
slow = fast;
fast = fastPrev;
}
return head;
}
};