Created
May 16, 2020 17:46
-
-
Save Gowtham-369/049bdfd33657f644b919e73b8303ed95 to your computer and use it in GitHub Desktop.
Day 15:LeetCode 30 Day May challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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) { | |
if(head == NULL) | |
return head; | |
ListNode* odd = head; | |
ListNode* evennode = head->next; | |
ListNode* even = evennode; | |
while(even!=NULL && even->next != NULL){ | |
odd->next = (odd->next)->next; | |
even->next = (even->next)->next; | |
odd = odd->next; | |
even = even->next; | |
} | |
//combining two lists | |
odd->next = evennode; | |
return head; | |
} | |
}; | |
/* | |
ListNode* GetnewNode(int data){ | |
ListNode* temp = new ListNode(data); | |
return temp; | |
} | |
ListNode* Insert(ListNode* root,int data){ | |
//create new node | |
ListNode* temp = GetnewNode(data); | |
if(root == NULL){ | |
root = temp; | |
return root; | |
} | |
//Inserting at tail | |
ListNode* temp_1 = root; | |
while(temp_1->next != NULL){ | |
temp_1 = temp_1->next; | |
} | |
temp_1->next = temp; | |
return root; | |
} | |
ListNode* oddEvenList(ListNode* head) { | |
//create odd group linkedlist(1->3->5->....) | |
//create even group linkedlist(2->4->6->8...) | |
//concatenate them | |
if(head == NULL) | |
return head; | |
ListNode* temp = head; | |
//root node must be pointed to null | |
ListNode* root_1 = NULL; | |
ListNode* root_2 = NULL; | |
int turn = 1; | |
while(temp != NULL){ | |
if(turn%2 == 0){ | |
//even nodes list | |
root_2 = Insert(root_2,temp->val); | |
} | |
else{ | |
//odd nodes list | |
root_1 = Insert(root_1,temp->val); | |
} | |
temp = temp->next; | |
turn+=1; | |
} | |
//joining two lists | |
ListNode* temp_1 = root_1; | |
while(temp_1->next != NULL){ | |
temp_1 = temp_1->next; | |
} | |
temp_1->next = root_2; | |
return root_1; | |
} | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. | |
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. | |
Example 1: | |
Input: 1->2->3->4->5->NULL | |
Output: 1->3->5->2->4->NULL | |
Example 2: | |
Input: 2->1->3->5->6->4->7->NULL | |
Output: 2->3->6->7->1->5->4->NULL | |
Note: | |
The relative order inside both the even and odd groups should remain as it was in the input. | |
The first node is considered odd, the second node even and so on ... |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment