/**
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
**/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
ListNode odd = new ListNode();
ListNode oddNext = new ListNode();
odd.next = oddNext;
ListNode even = new ListNode();
ListNode evenNext = new ListNode();
even.next = evenNext;
int n = 1;
while(head != null){
ListNode next = new ListNode(head.val,null);
if(n%2 == 1){
oddNext.next = next;
oddNext = oddNext.next;
}else{
evenNext.next = next;
evenNext = evenNext.next;
}
head = head.next;
n++;
}
oddNext.next = even.next.next;
return odd.next.next;
}
}
