NC133 链表的奇偶重排

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    //方法一：空间复杂度为O(n)，时间复杂度为O(n)
    ListNode* oddEvenList(ListNode* head) {
        // write code here
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* new_head = new ListNode(-1);
        ListNode* cur = new_head;
        while (odd != nullptr)
        {
            ListNode* new_node = new ListNode(odd->val);
            cur->next = new_node;
            cur = new_node;
            if (odd->next != nullptr)
                odd = odd->next->next;
            else
                break;
        }
        while (even != nullptr)
        {
            ListNode* new_node = new ListNode(even->val);
            cur->next = new_node;
            cur = new_node;
            if (even->next != nullptr)
                even = even->next->next;
            else
                break;
        }
        return new_head->next;
    }
};

class Solution {
public:
    //方法二：空间复杂度为O(1)，时间复杂度为O(n)
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* tmp = even;
        while (odd->next && odd->next->next)
        {
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = tmp;
        return head;
    }
};