链表的奇偶重排

1.借助栈
借助栈存偶数次序和奇数次序的结点，再合并到一个链表，时间复杂度：O（n）；空间复杂度：O（n）
import java.util.*;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• public ListNode(int val) {
• this.val = val;
• }
• }
• /

public class Solution {
/*
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode oddEvenList (ListNode head) {
// write code here
if(head==null)//链表为空
return null;
Stack<listnode> s1=new Stack<>();//存奇数结点
Stack<listnode> s2=new Stack<>();//存偶数结点
ListNode p=head;
int num=1;
while(p!=null){
if(num%2==0)
s2.push(p);
else
s1.push(p);
num++;
p=p.next;
}
ListNode res=null;
//使用的是尾插法，应先插入偶数
while(!s2.empty()){
ListNode temp=s2.pop();
temp.next=res;
res=temp;
}
while(!s1.empty()){
ListNode temp=s1.pop();
temp.next=res;
res=temp;
}
return res;
}
}
2.分离结点后合并
大佬的思路，用两个结点，一个代表偶数，一个代表奇数，然后再奇数后接偶数结点，让奇数结点都排在了前面，最后再连接偶数结点，时间复杂度：O（n），空间复杂度：O（1）
import java.util.</listnode></listnode>;

/*

• public class ListNode {
• int val;
• ListNode next = null;
• public ListNode(int val) {
• this.val = val;
• }
• }
• /

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode oddEvenList (ListNode head) {
// write code here
if(head==null)//链表为空
return null;
ListNode evenHead=head.next;//代表偶数结点
ListNode odd=head,even=evenHead;
//odd只连接了奇数结点，even只连接了偶数结点
while(even!=null&&even.next!=null){
odd.next=even.next;
odd=odd.next;
even.next=odd.next;
even=even.next;
}
odd.next=evenHead;//链接偶数结点
return head;
}
}