将連結清單中的所有元素為奇數的節點移到元素為偶數節點的前面，并使奇數之間順序反轉，偶數之間順序反轉（創新工廠塗鴉移動面試題）

問題描述：将連結清單中的所有元素為奇數的節點移到元素為偶數節點的前面，并使奇數之間順序反轉，偶數之間順序反轉

示例：

交換前連結清單的順序 交換後連結清單的順序

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;
				} else
					p = p.next;
			} else {
				if (p.value != pj.value) {
					p1.next = p;
					p = p.next;
					p1 = p1.next;
					p1.next = null;
					f1=true;
				} else
					p = 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));
	}
}