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;

}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store