题解 | #链表的奇偶重排#
链表的奇偶重排
https://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3
方法1：两个队列，一个保存奇数节点，另一个保存偶数节点，最后奇数节点先出队，偶数节点再出对
public ListNode oddEvenList (ListNode head) {
// write code here
if(head==null)return null;
Queue<ListNode>queueOdd=new LinkedList<>();
Queue<ListNode>queueEven=new LinkedList<>();
int i=1;
ListNode cur=head;
while(cur!=null){
if(i%2==1)
queueOdd.offer(cur);
else
queueEven.offer(cur);
cur=cur.next;
i++;
}
head=queueOdd.poll();
cur=head;
while(!queueOdd.isEmpty()){
cur.next=queueOdd.poll();
cur=cur.next;
}
while(!queueEven.isEmpty()){
cur.next=queueEven.poll();
cur=cur.next;
}
cur.next=null;
return head;
}
方法2、双指针法，一个指针指向奇数节点，一个指针指向偶数节点
奇数节点借助偶数节点的next跳往下一个奇数节点，偶数节点也同理（由于循环中要借助evenN和evenN.next，所以需要保证他俩是非null的）
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;
ListNode oddN=head;
ListNode evenN=head.next;
ListNode evenHead=evenN;
//循环判断语句第二个结束条件evenN.next!=null有点难想
while(evenN!=null&&evenN.next!=null){
oddN.next=evenN.next;
oddN=oddN.next;
evenN.next=oddN.next;
evenN=evenN.next;
}
oddN.next=evenHead;
return head;
}
}
