题解 | #链表的奇偶重排#

思路：

当链表为空或只有一个结点时，则直接返回head;

用一个变量记录当前节点的编号，当编号为奇数时添加到奇数链表，偶数时添加到偶数链表，最后将偶数链表拼接到奇数链表中，返回奇数链表。

复杂度分析：

时间：O(n)，遍历一次链表即可

空间：O(1)，维护几个必要的指针，是常数级变量空间

import java.util.*;

public class Solution {

public ListNode oddEvenList (ListNode head) {
    // write code here
    if(head==null || head.next==null)
        return head;
    int cnt = 1; //记录当前节点的编号
    ListNode odd_result = new ListNode(0);//奇数链表的头指针
    ListNode odd = odd_result;
    ListNode even_result = new ListNode(0);//偶数链表的头指针
    ListNode even = even_result;
    ListNode p = head;
    //遍历链表
    while(p!=null){
        if((cnt&1)==1){ //奇数编号，入odd链表
            odd.next = p;
            odd = odd.next;//odd指针右移
        } else { //偶数编号，入even链表
            even.next = p;
            even = even.next;//even指针右移
        }
        p = p.next;
        cnt++;//编号加1
    }
    even.next = null;//因为偶数链表在后，所以最后要指向null
    odd.next = even_result.next;//最后将偶数链表拼接到奇数链表中
    return odd_result.next;//完毕
}

}