[NC]133. 链表的奇偶重排

🚩传送门：牛客题目

题目

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

数据范围：节点数量满足 ，节点中的值都满足
要求：空间复杂度 ，时间复杂度

示例1

输入：{1,2,3,4,5,6} 返回值：{1,3,5,2,4,6} 说明： 重排前：1->3->5->2->4->6->NULL 重排后：1->2->3->4->5->6->NULL

解题思路：模拟

• head 指向原链表的表头
• odd 指向奇数链表的头结点
• oddTail 指向奇数链表的尾结点
• even 指向偶数链表的头结点
• evenTail 指向偶数链表的尾结点

1. 利用 head 依次遍历原来的链表结点
   • 若原链表不空，将 head 结点先插入 odd 链表中，利用 oddTail 在 操作时间内完成
   • 若原链表不空，将 head 结点后插入 even 链表中，利用 evenTail 在 操作时间内完成
2. 将 odd 链表和 even 链表合并，利用 oddTail 与 even 在 操作时间内完成

复杂度分析

时间复杂度：，其中 为合并后数组的长度。

空间复杂度：，使用常数的空间

我的代码

public ListNode oddEvenList (ListNode head) {
    // write code here
    if(head==null) return head;
    // 奇数头结点,尾指针
    ListNode odd=new ListNode(-1);
    ListNode oddTail=odd;
    //偶数头结点,尾指针
    ListNode even=new ListNode(-1);
    ListNode evenTail=even;
    while(head!=null){
        // 先穿奇
        if(head!=null){
            oddTail.next=head;
            oddTail=oddTail.next;
            head=head.next;
        }
        // 后穿偶
        if(head!=null){
            evenTail.next=head;
            evenTail=evenTail.next;
            head=head.next;
        }
    }
    // 先奇后偶拼接
    oddTail.next=even.next;
    evenTail.next=null;
    return odd.next;
}