Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on ...

328 Odd Even Linked List

练手的two pointer操作
将linkedlist根据 基偶位置重新排布，不创造额外空间

1 -> 2 -> 3 -> 4 -> 5
p1 = node 1
p2 = node 2
当后面还有剩余的时候我们每次将值写进去一个位置，然后将p向后移动两个
逻辑很简单，但是对于linkedlist一定要熟练

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if not head or not head.next:
            return head

        # now menas at least two elemnt in the array

        odd = head

        even = head.next

        otemp = odd
        etemp = even

        e1 = True
        e2 = True
        while e1 or e2:
            # print "this is odd"
            # print(odd)
            #
            # print "this is even"
            # print(even)
            if otemp.next and otemp.next.next:
                # if there is the next odd index node
                otemp.next = otemp.next.next
                otemp = otemp.next
            else:
                if otemp:
                    otemp.next = None
                e1 = False
            if etemp.next and etemp.next.next:
                # if there is the next even index node
                etemp.next = etemp.next.next
                etemp = etemp.next
            else:
                if etemp:
                    etemp.next = None
                e2 = False
        otemp.next =even
        print(odd)
        return odd

OJ上显示我速度beat 7% only，好奇..说明有更快的算法，估计是有更多的优化，因为我的算法处理even 和odd的重复，肯定有办法将其缩减到一个。。while.. too lazy...