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

<?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
function oddEvenList( $head )
{
    if($head == null || $head->next == null || $head->next->next == null){
        return $head;
    }
    $oddHead = $head;
    $evenHead = $head->next;
    $oddPre = null;
    $odd = $head;
    $even = $head->next;
    while($even != null && $odd != null){
        $odd->next = $even->next;
        $oddPre = $odd;
        $odd = $odd->next;
        if($odd == null){
            break;
        }
        $even->next = $odd ->next;
        $even = $even->next;
    }
    if($even == null){
        $odd->next = $evenHead;
    }else{
        $oddPre->next = $evenHead;
    }
    return $oddHead;
}

空间O(1), 时间O(n)

使用奇偶数两个指针，一次遍历把链表分成奇数列和偶数列，之后连接。