# Simple Python Solutions with Comments: O(1) Space, O(N) Time

• ``````#==============================================================================
# Solution 1:
# since the numbers are totally irrelavent, instead of looking at numbers,
# look at the linekd list as this format:
# odd1 -> even1 -> odd2 -> even2 -> odd3 with odd ending
# OR
# odd1 -> even1 -> odd2 -> even2 -> odd3 -> even3 with even ending
# record the head for odd and the head for even, then update their next accordingly
# in the end, remember to update the next of last odd to the first even
# Time: O(N)
# Space: O(1)
#==============================================================================
class Solution1(object):
"""
:rtype: ListNode
"""
while even:
if even.next is None:
break
else:
odd.next= even.next
odd = odd.next
even.next = odd.next
even = even.next
if even is None:
#==============================================================================
# Solution 2:
# Same idea as Solution 1, a bit cleaner, but a bit slower.
# Time: O(N)
# Space: O(1)
#==============================================================================
class Solution2(object):
"""
:rtype: ListNode
"""