leetcode 328. Odd Even Linked List

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 ...

还算简单的一道题。但是我貌似不符合 O(1) 空间复杂度 和 O(nodes) 时间复杂度。

package leetcode;

public class Odd_Even_Linked_List_328 {

	public ListNode oddEvenList(ListNode head) {
		if(head==null){
			return null;
		}
		if(head.next==null) {
			return head;
		}
		ListNode oddHead=getOddList(head);
		//切掉头元素，之前的偶数列就是 切掉头元素之后的奇数列
		ListNode evenHead=getOddList(head.next);
		
		ListNode oddTail=oddHead;
		while (oddTail.next!=null){
			oddTail=oddTail.next;
		}
		oddTail.next=evenHead;
		return oddHead;		
	}
	
	public ListNode getOddList(ListNode head){	
		ListNode result=new ListNode(head.val);
		ListNode node=result;
		boolean isOdd=false;
		head=head.next;
		while(head!=null){
			if(isOdd){
				node.next=new ListNode(head.val);
				node=node.next;
			}
			isOdd=(isOdd==true)?false:true;
			head=head.next;
		}
		return result;
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Odd_Even_Linked_List_328 o=new Odd_Even_Linked_List_328();
		ListNode head=new ListNode(1);
		head.next=new ListNode(2);
		head.next.next=new ListNode(3);
		head.next.next.next=new ListNode(4);
		head.next.next.next.next=new ListNode(5);
		ListNode result=o.oddEvenList(head);
		while(result!=null){
			System.out.print(result.val+" ");
			result=result.next;
		}
	}

}

大神写了符合O(1) 空间复杂度 和 O(nodes) 时间复杂度的过程：https://leetcode.com/problems/odd-even-linked-list/#/solution

使用四个变量来记录奇数链表的头和尾，偶数链表和头和尾。 
head：奇数链表的头
odd：奇数链表的尾
evenHead：偶数链表的头
even：偶数链表的尾
该算法遍历原始链表，把奇数结点放入奇数链表，把偶数结点放入偶数链表。为了遍历一个链表，我们需要在遍历过程中有一个指针来不停指向当前元素，因此这里的odd和even还充当了遍历指针这个角色。
以下是图解:

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(odd.next != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}