/**
給定單鏈表的頭節(jié)點?head?呛哟，將所有索引為奇數(shù)的節(jié)點和索引為偶數(shù)的節(jié)點分別組合在一起刨仑，然后返回重新排序的列表析珊。
第一個節(jié)點的索引被認為是 奇數(shù) 贝椿， 第二個節(jié)點的索引為?偶數(shù) ，以此類推曾沈。
請注意这嚣，偶數(shù)組和奇數(shù)組內部的相對順序應該與輸入時保持一致。
你必須在?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;
????}
}
