text: #
  # @lc app=leetcode id=328 lang=python
  #
  # [328] Odd Even Linked List
  #
  # https://leetcode.com/problems/odd-even-linked-list/description/
  #
  # algorithms
  # Medium (48.16%)
  # Likes:    856
  # Dislikes: 235
  # Total Accepted:    160.4K
  # Total Submissions: 320.6K
  # Testcase Example:  '[1,2,3,4,5]'
  #
  # 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 ...
  # 
  # 
  #
  # Definition for singly-linked list.
  
  
  class ListNode(object):
      def __init__(self, x):
          self.val = x
          self.next = None
  
      def __str__(self):
          return "<ListNode %s -> %s>" % (self.val, self.next)
  
  
  class Solution(object):
      def oddEvenList(self, head):
          """
          :type head: ListNode
          :rtype: ListNode
          """
          if not head:
              return
  
          guard = ListNode(0)
          odd = guard
          even_head = ListNode(0)
          even = even_head
          index = 1
          while head:
              if index % 2:
                  odd.next = head
                  odd = odd.next
              else:
                  even.next = head
                  even = even.next
              index += 1
              head = head.next
          odd.next = even_head.next
          even.next = None
          return guard.next
  
  
  # if __name__ == '__main__':
  #     s = Solution()
  #     head = ListNode(1)
  #     head.next = ListNode(2)
  #     head.next.next = ListNode(3)
  #     head.next.next.next = ListNode(4)
  #     head.next.next.next.next = ListNode(5)
  #     print s.oddEvenList(head)
  