问题描述：将链表中的所有元素为奇数的节点移到元素为偶数节点的前面，并使奇数之间顺序反转，偶数之间顺序反转
示例：
交换前链表的顺序 交换后链表的顺序
4→5→7→1→6==> 1→7→5→6→4
1 ==> 1 （链表仅含一个元素)
2→1 ==>1→2
==> (链表为空)
C/C++:
链表节点定义为：
struct node {
struct node *next;
int value;
};
struct node *swap(struct node *list);
Java:
链表节点定义为：
class Node {
public Node next;
public int value
}
Node swap(Node list)
注意点和要求如下:
1. swap函数要求对节点的指针/引用进行操作（不得创建任何新的链表节点）
2. 不得使用任何库函数/API，如需使用类似功能, 请自行实现
3. 不得将链表转化为其他类型数据结构再进行交换，如数组等
解题思路：具体思路是，将整个链表拆分为奇数链表和偶数链表两部分，然后把这两个子链表反转，最后把偶数链表接到奇数链表后面即可。具体java代码如下：
import java.util.*;class Node { // 链表节点的定义public int value;public Node next;}public class exam1 {public static Node create() { // 用来创建一个链表，用来测试的Node phead = new Node();Scanner scan = new Scanner(System.in);int n = scan.nextInt();phead.value = scan.nextInt();phead.next = null;Node p = phead;n--;while ((n--) > 0) {Node node = new Node();node.value = scan.nextInt();node.next = null;p.next = node;p = node;}return phead;}public static void print(Node phead) { // 打印链表，用来测试的while (phead != null) {System.out.print(phead.value + "->");phead = phead.next;}System.out.println();}public static Node swap(Node list) { // 按要求变换链表if(list==null)return list;Node p = list;Node pj = null;//奇数链表头Node po = null;//偶数链表头while (p != null) {//寻找奇数和偶数链表头if (pj == null && p.value % 2 != 0)pj = p;if (po == null && p.value % 2 == 0)po = p;p = p.next;}if(po==null) return reverseList(pj); //链表中没有偶数if(pj==null) return reverseList(po); //链表中没有奇数p = list;Node p1 = pj, p2 = po;boolean f1=false,f2=false;//f1用来标记链表中是否只有一个奇数节点，f2用来标记链表中是否只有一个偶数节点while (p != null) { //拆分成奇数和偶数链表if ((p.value & 1) == 0) {if (p.value != po.value) {p2.next = p;p = p.next;p2 = p2.next;p2.next = null;f2=true;} elsep = p.next;} else {if (p.value != pj.value) {p1.next = p;p = p.next;p1 = p1.next;p1.next = null;f1=true;} elsep = p.next;}}if(!f1)pj.next=null;if(!f2)po.next=null;pj = reverseList(pj); //分别反转奇数链表和偶数链表po = reverseList(po);p = pj;while (p.next != null) {p = p.next;}p.next = po; //将偶数链表接到奇数链表后面return pj;}public static Node reverseList(Node head) { // 反转链表Node pre = null;Node next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}public static void main(String[] args) {Node phead = create();print(phead);print(swap(phead));}}
将链表中的所有元素为奇数的节点移到元素为偶数节点的前面 并使奇数之间顺序反转 偶数之间顺序反转（创新工厂涂鸦移动面试题）
