###### tags: `leetcode` `medium` `Linked List`
# [328. Odd Even Linked List](https://leetcode.com/problems/odd-even-linked-list/description/)

## Description

Given the `head` of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return *the reordered list*.

The **first** node is considered **odd**, and the second node is **even**, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in `O(1)` extra space complexity and `O(n)` time complexity.

## Examples
### Example1

**Input**: head = [1,2,3,4,5]
**Output**: [1,3,5,2,4]

### Example 2:

**Input**: head = [2,1,3,5,6,4,7]
**Output**: [2,3,6,7,1,5,4]

## Constraints:

- The number of nodes in the linked list is in the range $[0, 10^4]$
- $-10^6 \leq Node.val \leq 10^6$ .

## Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LISTNODE;

struct ListNode* oddEvenList(struct ListNode* head) {
    // Under three node just return list
    if ((!head) || (!head->next) || (!head->next->next))
        return head;
    // Initialize pointers
    LISTNODE *lastOdd = head, *firstEven = lastOdd->next,
             *lastEven = lastOdd->next;
    // Run until find the last odd node or the last even node
    while (lastEven && lastEven->next) {
        // Find the next odd node
        lastOdd = lastOdd->next = lastEven->next;
        // Add even node to even-list
        lastEven = lastEven->next = lastOdd->next;
    }
    // Concate the odd list and even  list
    lastOdd->next = firstEven;
    return head;
}

## Complexity

|Space |Time |
|- |- |
|$O(1)$|$O(N)$|

## Result

- Runtime: 4 ms, 92.68%
- Memory: 7.1 MB, 25.30%