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


  • 0
    W
    #==============================================================================
    # 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):
        def oddEvenList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return head
            oddhead, odd = head, head
            evenhead, even = head.next, head.next
            while even:
                if even.next is None:
                    odd.next = evenhead
                    break
                else:
                    odd.next= even.next
                    odd = odd.next
                    even.next = odd.next
                    even = even.next
            if even is None:
                odd.next = evenhead 
            return oddhead 
    #==============================================================================
    # Solution 2:
    # Same idea as Solution 1, a bit cleaner, but a bit slower.
    # Time: O(N)
    # Space: O(1)
    #==============================================================================
    class Solution2(object):
        def oddEvenList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is None:
                return head
            oddhead, odd = head, head
            evenhead, even = head.next, head.next
            while even and even.next:
                odd.next= even.next
                odd = odd.next
                even.next = odd.next
                even = even.next
            odd.next = evenhead 
            return oddhead

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.