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

时间复杂度O(n)，空间复杂度O(1)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    // 先奇后偶
    ListNode* oddEvenList(ListNode* head) {
      if (head == nullptr || head->next == nullptr) {
        return head;
      }
      
      ListNode *odd_head = head, *even_head = head->next, *cur = head->next->next;
      odd_head->next = even_head->next = nullptr;
      ListNode *odd = odd_head, *even = even_head;
      int index = 1;
      
      while (cur) {
        ListNode *tmp = cur->next;
        cur->next = nullptr;
        if (index % 2) {
          odd->next = cur;
          odd = odd->next;
        } else {
          even->next = cur;
          even = even->next;
        }
        index++;
        cur = tmp;
      }
      
      odd->next = even_head;
      
      return odd_head;
    }
};