328. Odd Even Linked List

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 …

解法1：

考虑1->2->3->4这个情况，实际上只需要修改成1->3->4,2->4就可以了，然后把odd指针往下移动一格，even指针往下移动一格就可以了。
C++

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {

        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }

        ListNode oddHead = head, evenHead = head.next;
        ListNode odd = oddHead, even = evenHead;

        while (even != null && even.next != null) {
            ListNode temp = even.next;
            even.next = even.next.next; // skip next odd following the current even
            odd.next = temp;
            odd = odd.next;
            even = even.next;
        }

        // odd point to the tail of the list
        odd.next = evenHead;
        return oddHead;        
    }
}

另一种写法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode odd = new ListNode(1);
        ListNode even = new ListNode(2);
        ListNode odd_tail = odd;
        ListNode even_tail = even;
        int i = 1;
        while (head != null) {
            if (i % 2 == 1) {
                odd_tail.next = head;
                odd_tail = odd_tail.next;
            } else {
                even_tail.next = head;
                even_tail = even_tail.next;
            }
            head = head.next;
            i++;
        }

        odd_tail.next = even.next;
        even_tail.next = null;
        return odd.next;

    }
}