Python solution with two pointers O(N)


  • 7
    B
    # 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 not head:
                return head
            odd=head
            even=head.next
            while even and even.next!=None:
                temp = even.next
                even.next = even.next.next
                temp.next = odd.next
                odd.next = temp
                odd=odd.next
                even=even.next
            return head
    

    read in two node at a time:

    first node(odd) goes into odd.next
    2nd node(even).next = next even node (node.next.next)

    rinse and repeat

    so basically

    1 - 2 - 3 - 4- 5- 6 -7-null
    odd = 1 even = 2
    temp = 3
    even(2).next = even.next.next(4)
    temp(3).next=odd(1).next(2)
    (this makes sure the end of odd always points to start of even)
    odd(1).next = temp(3)
    odd = odd.next(3) move the pointer
    even = even.next(4) move the pointer

    1-3(odd)-2-4(even)-5-null

    1-3-5(odd)-2-4-null(even)

    1-3-5-7(odd)-2-4-6-null(even)


  • 0
    H

    Can you explain?


  • 0
    B

    updated answer with comments


  • 0
    K

    Hi BioDaddy -- can you help clarify the 'temp.next=odd.next' line?
    How does odd point back to 2?

    for the sequence 1->2->3->4->5->NULL
    I'm see it as: 1->3->5->4-NULL
    because that temp is at 5 and goes to 4, temp(5).next=odd(3).next(4)


  • 0
    B

    hi Kenny7

    think of it as head -----------> odd (tail of odd) ->(beggining of even:2)------->even(variable)->temp(variable)----->tail->null

    you want to put the temp variable between end of odd (the odd variable) and the beginning of even because your temp is the next odd

    it's very similar to 141. Linked List Cycle


  • 0
    C

    no need for !=None

    while even and even.next!=None:

    Just

    while even and even.next:

    should be fine


  • 0
    J

    Here is the modified version. If we do odd first, there is no need to record tmp.

    class Solution(object):
        def oddEvenList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if not head or not head.next: return head
            odd=head
            even=head.next
            evenhead=head.next
            while even and even.next:
                odd.next=odd.next.next
                odd=odd.next
                even.next=even.next.next
                even=even.next
            odd.next=evenhead
            return head
    

Log in to reply
 

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