hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Odd Even Linked List


  • Approach:

    1. Declared two pointers namely oddHead and evenHead, which respectively denotes the head of the list of the odd Nodes and similarly for the even nodes.

    2. Then traverse through the given linked list and added 1st, 3rd, 5th, .... etc nodes to the oddList and 2nd, 4th, 6th, .... etc nodes to evenList.

    3. Connected the oddList's end with evenList's head.


  • Time and Space Complexity:

    • Time complexity: O(n)

    • Space complexity: O(1)


Code [C++]

/**

* 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) {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

if(!head || !head->next || !head->next->next) return head;

ListNode * oddHead = head, *evenHead = head->next;

ListNode * curOdd = oddHead, *curEven = evenHead;

head = head->next->next;

while(true){

if(!head) break;

curOdd->next = head;

head = head->next;

curOdd = curOdd->next;

curOdd->next = NULL;



if(!head) break;

curEven->next = head;

head = head->next;

curEven = curEven->next;

curEven->next = NULL;

}

curEven->next = NULL;

curOdd->next = evenHead;

return oddHead;

}

};