328.OddEvenLinkedList.cpp

/*
 * @lc app=leetcode id=328 lang=cpp
 *
 * [328] Odd Even Linked List
 *
 * https://leetcode.com/problems/odd-even-linked-list/description/
 *
 * algorithms
 * Medium (57.01%)
 * Likes:    2810
 * Dislikes: 330
 * Total Accepted:    348.9K
 * Total Submissions: 611.9K
 * Testcase Example:  '[1,2,3,4,5]'
 *
 * Given a singly linked list, group all odd nodes together followed by the
 * even nodes. Please note here we are talking about the node number and not
 * the value in the nodes.
 * 
 * You should try to do it in place. The program should run in O(1) space
 * complexity and O(nodes) time complexity.
 * 
 * Example 1:
 * 
 * 
 * Input: 1->2->3->4->5->NULL
 * Output: 1->3->5->2->4->NULL
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: 2->1->3->5->6->4->7->NULL
 * Output: 2->3->6->7->1->5->4->NULL
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * The relative order inside both the even and odd groups should remain as it
 * was in the input.
 * The first node is considered odd, the second node even and so on ...
 * The length of the linked list is between [0, 10^4].
 * 
 * 
 */

// @lc code=start
/**
 * 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 || !head->next) {
            return head;
        }

        ListNode* odd_list_head = head;
        ListNode* even_list_head = head->next;

        ListNode* odd_list_tail = odd_list_head;
        ListNode* even_list_tail = even_list_head;

        ListNode* curr = head->next->next;
        int idx = 1;
        while (curr) {
            ListNode* next = curr->next;
            if (idx % 2) {
                odd_list_tail->next = curr;
                odd_list_tail = odd_list_tail->next;
            }
            else {
                even_list_tail->next = curr;
                even_list_tail = even_list_tail->next;
            }

            curr = next;
            idx = idx == 1 ? 0 : 1;
        }
        
        even_list_tail->next = nullptr;
        odd_list_tail->next = even_list_head;
        
        return odd_list_head;
    }
};
// @lc code=end