Even After Odd Linked List

#1

I solved this problem using the above code. But I am having trouble in finding out the time and space complexity of this code. Please help.

#2

@vaishnavtannu can you explain your logic in short so that can tell you about the time and space complexity

#3
  1. I created two new linked lists i.e. even and odd
  2. Then I iterated over the entire linked list that is given and if current value is odd, I pushed into odd otherwise even using insert function.
  3. Since odd linked should come before even, so i checked if odd is NULL, if yes then i make odd = even
  4. Just append even after odd
#4

@vaishnavtannu ok so time complexity should be o(n) where n is size of linklist and space is o(2*n) as two linklist are separately made so space also o(n)
hope its cleared if yes dont forget to hit like and mark resolved :smiley:

#5

Why time is O(n) since I am calling insert function inside while loop ?
What is the time complexity of insert function alone which is inserting data at tail?

#6

Please explain Why time is O(n) since I am calling insert function inside while loop ?
What is the time complexity of insert function alone which is inserting data at tail?

#7

@vaishnavtannu ok i saw your code you haven’t maintained a tail pointer so you always iterate to end so in your case time complexity becomes o(n*n) but generally if you do using link list stl or by maintaining tail insertion time is o(1)

#8

Yeah, that’s why I got confused. Can you please tell how can I convert the same code to work in o(n) time using stl ?

#9

@vaishnavtannu for that you need to know about list stl functions do you know about them?
they are just like vector you can create two even and odd and just simply push back into them
(https://www.geeksforgeeks.org/list-cpp-stl/)

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.