################################################################################
# Question:
# 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 1:

# Input: 1->2->3->4->5->NULL
# Output: 1->3->5->2->4->NULL
# Example 2:

# Input: 2->1->3->5->6->4->7->NULL
# Output: 2->3->6->7->1->5->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 ...
################################################################################
# Solution Notes:
# Time Complexity O(n)
# Space Complexity O(1)
# Traverse the list and extract the even nodes into another linked list
# Attach the tail of the original linked list which contains only the odd nodes
# to the head of the even linked list
################################################################################

# 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
        """
        odd_head = odd = head
        even_head = even = ListNode(0)
        odd_p = None
        while odd:
            even.next = odd.next
            odd.next = even.next.next if even.next else None
            odd_p = odd
            odd = odd.next
            even = even.next
        if odd_p:
            odd_p.next = even_head.next
        return odd_head
            