Python solution with two pointers O(N)

• ``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
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
``````

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)

• Can you explain?

• 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)

• 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

• no need for !=None

while even and even.next!=None:

Just

while even and even.next:

should be fine

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

``````class Solution(object):
"""
:rtype: ListNode
"""