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&nbsp;in O(1)&nbsp;extra space complexity and O(n) time complexity.

&nbsp;
Example 1:

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]


&nbsp;
Constraints:


	The number of nodes in the linked list is in the range [0, 104].
	-106 &lt;= Node.val &lt;= 106


class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return 
        odd, even_start, even = head, head.next, head.next
        while odd is not None and even is not None:
            odd.next = even.next
            if odd.next is not None:
                odd = odd.next
                even.next = odd.next
                even = even.next
            else:
                break
        odd.next = even_start
        return head
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null) {
            return head;
        }
        ListNode result = head, evenHalf = new ListNode(0), evenHalfPtr = evenHalf;
        for(; head.next != null; head = head.next) {
            evenHalfPtr = evenHalfPtr.next = head.next;
            head.next = head.next.next;
            evenHalfPtr.next = null;
            if(head.next == null) {
                break;
            }
        }
        head.next = evenHalf.next;
        return result;
    }
}
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL || head->next->next == NULL){
            return head;
        }
        ListNode *first = head;
        ListNode *second = head->next;
        ListNode *last = head;
        int count = 1;
        while(last->next != NULL){
            last = last->next;
            count++;
        }

        int n = count/2;
        while(n != 0){
            first->next = second->next;
            last->next = second;
            second->next = NULL;
            first = first->next;
            last = second;
            second = first->next;
            n--;
        }
        return head;
    }
};
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if (!head || !head.next) return head;
    let oddNode = head;
    const evenHead = head.next;
    let evenNode = head.next;
    
    while(evenNode?.next) {
        oddNode.next = evenNode.next;
        oddNode = oddNode.next;
        evenNode.next = oddNode.next;
        evenNode = evenNode.next;
    }
    
    oddNode.next = evenHead;
    
    return head;
};
Odd Even Linked List