Clear Python Solution


  • 23
    T
    def oddEvenList(self, head):
        dummy1 = odd = ListNode(0)
        dummy2 = even = ListNode(0)
        while head:
            odd.next = head
            even.next = head.next
            odd = odd.next
            even = even.next
            head = head.next.next if even else None
        odd.next = dummy2.next
        return dummy1.next

  • 0
    J

    Why do we not just return head instead of dummy1.next?
    I tried to return head, and I got the wrong answer.


  • 0
    P

    because head is not the head anymore, lol


  • 0
    C

    can u tell me what is the meaning of" odd = ListNode(0) "? and why do u assign "odd.next = dummy2.next"? and return dummy1.next?
    Thank you very much


  • 0
    Y

    head became None at the end


  • 0
    Y

    I try to explain your questions:
    The author solved this problem by using two linked lists, odd chain and even chain. "odd = ListNode(0)" and "even = ListNode(0)" get two nodes to build these two lists
    dummy1 is the head of odd lists and dummy2 is even, after the "while" statements odd is the tail of odd list, "odd.next = dummy2.next" is used to link two chains
    Even dummy1 is odd chain's head, but it's a "blank node", that is its val is meaningless, actually ,"dummy1.next" is the real head node, and it equals to the first node in the chain which question given us


  • 0
    C

    thank you so much, but "dummy.next" should be one number? how could it be a list?


  • 0
    Y

    Actually, dummy is a node, and dummy.next is so. If you catch a node, then you catch all the nodes that after it, they are linked by "next" pointer, you can get the second node by next, third by next.next, and so on. So I said you get a list
    Forgive my broken English =.=


  • 0
    S

    Thank you for the code. I have a bit different question here. In Leetcode they enter the input as an array and it worked for them. However, when I try to run that same code in local machine, that input is no longer valid. Can anybody points out, how to give a linked list input.

    Thanks in advance


  • 1
    F

    You can construct the linked list similar to the code above:

    def construct_linked_list(arr):
        input = dummy = ListNode(0)
        for num in arr:
            dummy.next = ListNode(num)
            dummy = dummy.next
        return input.next

  • 1
    T

    My first 96.38%, new to leetcode. Any suggestion is welcome.

    class Solution(object):
        def oddEvenList(self, head):
            if head is None: return None
            if head.next is None: return head
            o = head
            p = o.next
            ehead = p
            while p.next is not None:
                #t = o.next
                o.next = p.next
                p.next = p.next.next
                #o.next.next = t
                o = o.next
                p = p.next
                if p is None: break
                #if o is None: break
            o.next = ehead
            return head
    

  • 1
    M

    ANy idea why this solution is not working:

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def oddEvenList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head is not None:
                return head
                
            o = head
            e = head.next
            evenhead = e
            
            while e and e.next:
                o.next = o.next.next
                e.next = e.next.next
                o = o.next
                e = e.next
                
            o.next = evenhead
            return head
            
    

  • 1
    M

    @modqhx said in Clear Python Solution:

    ANy idea why this solution is not working:

    Well, first, I'm very impressed by the elegance of your solution - I have more None checks in mine, which evidently are superfluous.

    However, the one explicit None check you do have (presumably to protect from an empty input list) is the source of all your trouble: it instead protects from all non-empty lists. Remove the not and you're good to go!


  • 0
    C

    @modqhx

    I think o.next = o.next.next sets the o.next pointer and e.next is actually already pointing to o. So e.next points to the newly set o.next which is an odd numbered element hence creating the problem. So I think one could do:
    temp1 = o.next.next
    temp2 = e.next.next
    o.next = temp1
    e.next = temp2

    to solve the problem


  • 0
    H

    This is just brilliant, thx for your solution.


  • 0
    Z

    @tusizi said in Clear Python Solution:

        head = head.next.next if even else None
    

    what does " head = head.next.next if even else None" mean?


  • 0
    L

    Even easier solution. Not sure if follows the in place requirement, however.

    class Solution(object):
        def oddEvenList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            d1=odd=ListNode(0)
            d2=even=ListNode(0)
            i=1
            while head:
                if i%2:
                    odd.next,odd=head,head
                else:
                    even.next,even=head,head
                head=head.next
                i+=1
            odd.next,even.next=d2.next,None
            return d1.next

Log in to reply
 

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