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

//解法1
/*
使用两个指针来做,pre指向奇节点,cur指向偶节点,然后把偶节点cur后面的那个奇节点提前到pre的后面,然后pre和cur各自前进一步,此时cur又指向偶节点,pre指向当前奇节点的末尾,以此类推直至把所有的偶节点都提前了即可。
*/
class Solution {
public:
	node* oddEvenList(node* head) {
		if (!head || !head->next) return head;
		node *pre = head, *cur = head->next;
		while (cur && cur->next) {
			node *tmp = pre->next;
			pre->next = cur->next;
			cur->next = cur->next->next;
			pre->next->next = tmp;
			cur = cur->next;
			pre = pre->next;
		}
		return head;
	}
};
//解法2
/*
用两个奇偶指针分别指向奇偶节点的起始位置,另外需要一个单独的指针even_head来保存偶节点的起点位置,然后把奇节点的指向偶节点的下一个(一定是奇节点),此奇节点后移一步,再把偶节点指向下一个奇节点的下一个(一定是偶节点),此偶节点后移一步,以此类推直至末尾,此时把分开的偶节点的链表连在奇节点的链表后即可。
*/
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *odd = head, *even = head->next, *even_head = even;
        while (even && even->next) {
            odd = odd->next = even->next;
            even = even->next = odd->next;
        }
        odd->next = even_head;
        return head;
    }
};
#include <iostream>
using namespace std;

class node{
	public:
		int value;
		node * next;
	
	public:	
		node(int value = 0,node * next = NULL){
			this->value = value;
			this->next = next;
		}
};

int main(int argc, char *argv[]) {
	int m = 0;
	while(cin >> m){
		/*建立链表1*/
		node * head_first = new node();
		node * tail_first = head_first;
		for(int i = 0 ; i < m ; i ++){
			node * p = new node();
			int temp;
			cin >> temp;
			p->value = temp;	
			tail_first->next = p;
			tail_first = p;
		}
		/*输出链表1和2*/
		node * head_1 = head_first->next;
		while(head_1){
			cout << head_1->value << " ";
			head_1 = head_1->next;
		}
		cout << endl;
		
		
		/*输出新链表*/
		Solution * solution = new Solution();
		node * p = solution->oddEvenList(head_first->next);
		
		
		while(p){
			cout << p->value << " ";
			p = p->next;
		}
		cout << endl;
		
	}
}