1. 概述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

1.1 思路

1. 把链表分成三部分，前后不变中间反转，再将三部分合并成一个新的链表。

   2. 解题

   ```php <?php

class ListNode { public $val = 0; /* @var ListNode / public $next = null;

function __construct($val)
{
    $this->val = $val;
}

}

class Solution { /**

 * @param ListNode $head
 * @param Integer $m
 * @param Integer $n
 * @return ListNode
 */
public function reverseBetween($head, $m, $n) :? ListNode
{
    $dummy = new ListNode(0);
    $dummy->next = $head;
    /** @var ListNode $newDummy */
    $newDummy = NULL;
    /** @var ListNode $newHead */
    /** @var ListNode $newMiddleTail */
    /** @var ListNode $newMiddle */
    $newHead = $newMiddleTail = $newMiddle = NULL;
    $i = 0;
    while ($dummy->next) {
        $i++;
        if ($i < $m) {
            // 组成新链表
            if ($newHead) {
                $newHead->next = new ListNode($dummy->next->val);
            } else {
                $newHead = new ListNode($dummy->next->val);
            }
            $dummy = $dummy->next;
            continue;
        }
        if ($i > $n) break;
        // 删除中间元素
        $tmpNode = $dummy->next;
        $dummy->next = $dummy->next->next;
        // 创建 “新中间元素链表” ：取迭代元素插入 $newMiddle 头部
        $newMiddle && $tmpNode->next = $newMiddle;
        $newMiddle = $tmpNode;
        // 记录 “新中间元素链表” 尾部
        !$newMiddleTail && $newMiddleTail = $tmpNode;
        // 绑定尾部指针后边链表元素
        if ($i == $n) {
            $newMiddleTail->next = $dummy->next;
        }
    }
    // 新链表前部 与 新中间元素链表 合并
    if ($newMiddle) {
        $newHead->next = $newMiddle;
    } else {
        $newHead = $newMiddle;
    }
    return $newHead;
}

}

// 1->2->3->4->5 // 1->4->3->2->5 $head = new ListNode(1); $head->next = new ListNode(2); $head->next->next = new ListNode(3); $head->next->next->next = new ListNode(4); $head->next->next->next->next = new ListNode(5); $m = 2; $n = 4;

$cls = new Solution(); $ret = $cls->reverseBetween($head, $m, $n); print_r($ret); ```