92.md

✏️基础刷题之(92. Reverse Linked List) II)

. 2020-01-29 吴亲库里 库里的深夜食堂

✏️描述

从指定位置开始到指定位置结束反转这中间的链表。

✏️题目实例

​

---

✏️题目分析

像这类题目有可能头结点也会发生变动，但是给定的链表是没有固定的头指针的，所以我们一般会自己创建一个 dummy 的 node。这样的话即使头结点变动了，我们只需要使用 dummy->next 即可。我们还需要找到反转开始的前一个节点，因为反转结束之后我们需要把它和前面的链表连接起来。解题的方式有很多种，我这里主要列下代码执行的过程变化。链表类的题目最好自己动手。

1 -> 2 -> 3 -> 4 -> 5 -> NULL

1 -> 3 -> 2 -> 4 -> 5 -> NULL

1 -> 4 -> 3 -> 2 -> 5 -> NULL

✏️最终实现代码

**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @param Integer $m
     * @param Integer $n
     * @return ListNode
     */
    function reverseBetween($head, $m, $n) {
        $dummy=new ListNode(-1);
        $pre=$dummy;
        $dummy->next=$head;
        for($i=0;$i<$m-1;$i++){
            $pre=$pre->next;
        }
        $cur=$pre->next;
        for($i=$m;$i<$n;$i++){
            $t=$cur->next;
            $cur->next=$t->next;
            $t->next=$pre->next;
            $pre->next=$t;
        }
        return $dummy->next;
    }
}

联系

​