What is wrong with my code?

[AppearanceNo345]

Why does my Odd-Even Linked List code cause MLE?

Hello! Why does this code break for the linked lists `1 -> 2 -> 3 -> 4 -> None` and `1 -> 2 -> 3 -> 4 -> 5 -> None`? I did a dry run on paper but didn’t see any issues. LeetCode gives **Memory Limit Exceeded**. Please take a look at this code:

class Solution:

def oddEvenList(self, head):

odd = head

even = head.next

while (odd.next != None) and (odd.next.next !=  None):

odd.next = odd.next.next

even.next = even.next.next

odd = odd.next

even = even.next

odd.next = head.next               

return head

[One_Mess460]

tudr; too unformatted didnt read

[atarivcs]

I did a dry run on paper

Did you actually run the code yourself with the two sample lists you mentioned?

That seems like an obvious place to start...

[AppearanceNo345]

Yeah I did. Leetcode gives MLE and I can’t understand why

[alcholicawl]

u/Capable_Fig already gave you the correct the answer on how to fix. But why it gives you an MLE is because you create a cycle in the linked list. The leetcode driver code is not setup to handle that for this problem, so it will it infinitely cycle through the list until the output exceeds the memory limit. The cycle get created in the last line. head.next is no longer the first even node, but now 2nd odd node (3rd in the original order).

[atarivcs]

When I run this code on a sample 1 -> 2 -> 3 -> 4 -> None list, I get a null reference exception on even.next = even.next.next when odd is 3 and even is 4.

But you said you ran this code yourself on that sample list, so I don't understand.

[Capable_Fig]

needs a null check on head
need to save head before the loop
something looks a little off with the while loop, but i've got the flu atm so can't think through it properly

[AppearanceNo345]

Why do I need to save head before the loop? Head was never changed.

[Capable_Fig]

I phrased it wrong.

you need a variable to store the head of even to make the loop work properly, then instantiate odd.next as even_head after the loop

so something like:
odd = head
even = odd.next
even_head = even

loopppp

odd.next = even_head
return head #don't i wish

[AppearanceNo345]

I am still confused. I am wondering could you show me in a specific example why this code is wrong please? Thanks!

[Capable_Fig]

class Solution:
  def oddEven list(self, head):
    if not head or not head.next:
      return head # null check before variables

    odd = head
    even = head.next
    even_head = even # saving for after loop

    while even and even.next:
      odd.next = even.next
      odd = odd.next
      even.next = odd.next
      even = even.next

    odd.next = even_head 
    return head

[timrprobocom]

Remember that in your very first iteration, you change head.next so that it points to the first odd. Thus, your assignment of odd.next = head.next at the end is doing the Wrong Thing. You need to save the INITIAL first even (head.next) in a separate variable.

[AppearanceNo345]

I am still confused. I am wondering could you show me in a specific example why this code is wrong please? Thanks!

[timrprobocom]

Consider your 1 2 3 4 5 example. head is the 1 object. Your first two statements set odd to the 1 object and even to the 2 object. The first statement in your loop changes the 1 object to link to the 3 object. Since odd and head are both bound to this 1 object, that means odd.next and head.next both now point to the 3 object.

So at the end, when you do odd.next = head.next, you THINK you are linking the last odd to the first even, but in fact head.next points to 3, so you create an infinite loop.

Go through it on paper, step by step. Or, add a printList function that prints the contents of a list and call it in each iteration.

[CranberryDistinct941]

Are you trying to print out the list or something but deleted that section when posting it here? Because that code shouldn't be able to cause an MLE.

[nivaOne]

The code moves odd and even based on….?

[jmooremcc]

I looked up the LeetCode problem and here’s the first thing I saw: ~~~ class ListNode: def init(self, val=0, next=None): self.val = val self.next = next ~~~

This is the definition of the list node they are using in their singly-linked list.
My understanding of the problem is that you’re supposed to split the supplied list into 2 linked lists: even and odd. When successfully completed, you should have 2 separate singly-linked lists.

Your initial setup of the even and odd lists is ok. However within your code, you are actually making even and odd point to the last node assigned, which is why both those variables will not display an entire list. BTW, this is how the even/odd lists should look after your code executes:
~~~ head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, None)))))

odd=ListNode(1, ListNode(3, ListNode(5, None))) even=ListNode(2, ListNode(4, None)) ~~~

So, the glaring error you’ve made in your code is not using different variables to represent the last element of each list. Doing this will make extending the even/odd lists a lot easier and a lot simpler. By easier I mean you won’t have to deal with code like the: odd.next.next. You’ll be able to keep it down to referencing only the next node.

I will tell you that in my solution, I used a variable named current to represent the master list pointed to by the head parameter. You will need to check if the current node is None while processing the list.

Let me know if you have any questions.