题解 | #链表内指定区间反转#

<?php

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param m int整型 
 * @param n int整型 
 * @return ListNode类
 */
function reverseBetween( $head ,  $m ,  $n )
{
    // write code here
    if($head == null || $head->next == null){
        return $head;
    }
    $beg = $head;
    $pre = null;
    $pos = 1;
    while($pos < $m){
        $pre = $beg;
        $beg = $beg->next;
        $pos++;
    }
    $reverseBeg = $beg;
    $temp= $beg;
    while($pos <= $n){
        $temp = $beg->next;
        $beg->next = $pre;
        $pre = $beg;
        $beg = $temp;
        $pos ++;
    }
    $temp = $reverseBeg->next;
    $reverseBeg->next = $beg;
    if($temp != null){
        $temp->next = $pre;
        return $head;
    }else{
        return $pre;
    }
    
}

思路：

1. 新增beg和pre指针，while循环使beg指向第m个节点，pre指向beg前一个指针
2. 用reverseStart指针记录第m节点，beg和pre用while循环至第n个节点，用普通反转链表法反转m到n的链表
3. 反转结束后，beg指向第n+1个节点，pre指向第n个节点。第m个节点指向beg节点，第n个节点需要判断第一个节点是否为null，不为null指向m-1个节点，返回head（最初指向第一个节点的指针），为null直接返回第m个节点。