2.将链表中的所有元素为奇数的节点移到元素为偶数节点的前面，并保证奇数之间顺序不变，偶数之间顺序不变。
示例：
交换前链表的顺序 交换后链表的顺序
4→5→3→1→2 ==> 5→3→1→4→2
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. 不得将链表转化为其他类型数据结构再进行交换，如数组等
package offer;
/**
* 树结构
* @author cxx
*
*/
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
ListNode() {
}
}
package offer;
/**
* 将链表中的所有元素为奇数的节点移到元素为偶数节点的前面，并保证奇数之间顺序不变，偶数之间顺序不变。
* @author cxx
*
*/
public class Main {
public static void main(String[] args) {
ListNode listNde1 = new ListNode(4);
ListNode listNde2 = new ListNode(5);
ListNode listNde3 = new ListNode(3);
ListNode listNde4 = new ListNode(1);
ListNode listNde5 = new ListNode(2);
listNde1.next = listNde2;
listNde2.next = listNde3;
listNde3.next = listNde4;
listNde4.next = listNde5;
Main main = new Main();
ListNode listNde = main.swap(listNde1);
// 53142
while (listNde != null) {
System.out.println(listNde.val);
listNde = listNde.next;
}
}
/**
* 链表元素的交换方法 奇数的节点移到元素为偶数节点的前面
* 1.查找尾元素，确定程序的结束点
* 1.找到第一个奇数元素，并将该元素之前的偶数放到尾部
*
*
*
* @param listNode
* @return
*/
public ListNode swap(ListNode listNode) {
if(listNode == null){
return null;
}
if(listNode.next == null){
return listNode;
}
ListNode end = listNode;//尾元素
ListNode prev = null;//指针移动的前一个节点
ListNode curr = listNode;//指针移动的当前节点
/**
* 循环，查找尾节点
*/
while (end.next != null) {
end = end.next;
}
ListNode newEnd = end;// 新的尾节点，不断的存放接收的偶数元素。
// 将第一个奇数前的偶数放到链尾
while (curr.val % 2 == 0 && curr != end) {
newEnd.next = curr;
curr = curr.next;
newEnd.next.next = null;
newEnd = newEnd.next;
}
// 元素是奇数
if (curr.val % 2 != 0) {
/* 头结点为第一个奇数 */
listNode = curr;
while (curr != end) {
if ((curr.val) % 2 != 0) {//奇数
prev = curr;
curr = curr.next;
} else {
// 将pre指向后一个节点
prev.next = curr.next;
curr.next = null;
newEnd.next = curr;// 将当前的偶数放到链尾
// 链尾后移
newEnd = curr;
// 继续判断
curr = prev.next;
}
}
} else {
//根据理论，此时curr只有可能是尾节点，有while (curr.val % 2 == 0 && curr != end) 判断
prev = curr;
}
// 尾节点的特殊处理
if ((end.val) % 2 == 0) {
prev.next = end.next;
end.next = null;
newEnd.next = end;
}
return listNode;
}
}