# 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
1 - 2 - 3 - 4- 5- 6 -7-null
odd = 1 even = 2
temp = 3
even(2).next = even.next.next(4)
(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
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)
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:
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): 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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.