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

题目：链表的奇偶重排

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

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

示例1：输入：{1,2,3,4,5,6}，返回值：{1,3,5,2,4,6}

说明：1->2->3->4->5->6->NULL重排后为1->3->5->2->4->6->NULL

示例2：输入：{1,4,6,3,7}，返回值：{1,6,7,4,3}

说明：1->4->6->3->7->NULL重排后为1->6->7->4->3->NULL
奇数位节点有1,6,7，偶数位节点有4,3。重排后为1,6,7,4,3

解法一：

思路分析：根据题目分析，将一个单链表的奇数位结点先存放完，然后再存放单链表的偶数位结点（是编号而非数值），所以我们只需要找出链表的奇偶数位，然后分别存放进去即可，所以我们可以声明一个evenHead的链表指向head的下一位，然后新建一个odd链表和even链表，odd = head，even = evenHead，只需要一直循环判断even链表的值是否为空即可停止循环，先将odd中的奇数位摘录出来，然后用evenhead保存偶数位，在循环停止的时候，将evenhead中的元素保存到odd的后边即可。

实例分析：输入：{1,2,3,4,5,6}
图片说明
第一次循环：

第二次循环：

第三次循环：

最后跳出循环：

java核心代码为：

import java.util.*;

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

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode evenHead = head.next;//设置偶数标记链表
        ListNode odd = head, even = evenHead;
        while (even != null && even.next != null) {
            odd.next = even.next;//1->3，依次循环
            odd = odd.next;//首指针指向3，依次循环
            even.next = odd.next;//2->4，依次循环
            even = even.next;//首指针指向4，依次循环
        }
        odd.next = evenHead;//奇数排完了，将偶数位的排在奇数位后边
        return head;
    }
}

本程序在运行中，需要将所有的偶数位的结点访问一次，所以其时间复杂度为 $O(N/2 - 1)$ ，即 $O(N)$ 。在内存方面，并未申请新空间，所以其空间复杂度位 $O(1)$ 。

解法二：

思路分析：根据上面思路分析，这次我们可以采用划分链表的方法，还是单独的将奇数序列设置为odd，将偶数序列设置为even，不过将这些链表设置为0开头的，之后新建一个p指针，用来指需要存储的奇数位和偶数位，当找到奇数位，将该数放入odd中，找到偶数位，将偶数位放到even中，经过循环，最后将odd.next指向evenhead.next，就将所有奇偶数位整合到了一起。

具体java代码如下所示：

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
            ListNode oddhead = new ListNode(0);//用来存储奇数序列
            ListNode evenhead = new ListNode(0);//用来存储偶数序列
            ListNode odd = oddhead, even = evenhead, p = head;

            while (p != null) {
                odd.next = p;//计算得到奇数
                odd = p;
                p = p.next;
                odd.next = null;//将每次循环后的奇数后面的元素去掉

                if (p == null)
                    break;
                even.next = p;//计算得到偶数
                even = p;
                p = p.next;
                even.next = null;//将偶数后面的元素去掉
            }
            odd.next = evenhead.next;//整合起来
            return oddhead.next;
        }
}

因为需要用p指针循环指向链表中的所有元素，所以其时间复杂度为 $O(N)$ ，不需要建立额外的内存空间，只申请了两个头节点空间，所以空间复杂度为 $O(1)$ 。