# Day 16 of 31-Day May LeetCode Challenge

`/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* oddEvenList(ListNode* head) {                if(head==NULL||head->next==NULL) return head;        //         //method 1 : O(n) time & O(n) space  -> 35 %//         ListNode *odd = new ListNode(-1);   //added a dummy node in the beginning//         ListNode *even = new ListNode(-1);  //added a dummy node in the beginning        //         ListNode *myHead = odd;        //         //creating odd linked list//         ListNode *temp = head;//         while(true){//             odd->next = new ListNode(temp->val);//             odd = odd->next;//             if(temp->next!=NULL&&temp->next->next!=NULL){//                 temp = temp->next->next;//             }else break;//         }//         //creating even linked list//         ListNode *evenHead = even;//         ListNode *temp2 = head->next;//         while(true){//             even->next = new ListNode(temp2->val);//             even = even->next;//             if(temp2->next!=NULL&&temp2->next->next!=NULL){//                 temp2 = temp2->next->next;//             }else break;//         }//         //linking odd & even list//         odd->next = evenHead->next;        //         return myHead->next;                        //method 2 : O(n) time & O(1) space -> 95 %        //hint 1 : we need to make odd & even linked list SIMULTANOUSLY        //hint 2 : we need 4 pointers        ListNode *odd = head;        ListNode *even = head->next;        ListNode *evenHead = even;        ListNode *oddHead = odd;                while(even!=NULL&&even->next!=NULL){            odd->next = even->next;            even->next = even->next->next;                        odd = odd->next;            even = even->next;        }        odd->next = evenHead;                return oddHead;            }};`