LeetCode 解题报告-92. 反转链表 II

Leetcode 第 92. Reverse Linked List II 题，题目难度 Medium。

一. 题目要求

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

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

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

本题是 206.反转链表 的进阶版，要求反转指定范围内的部分链表。实现思路如下：

• 找到索引 m 处 node 的前一个 preNode
• 反转 m 到 n 区间的链表
• 处理边界：原来的 preNode 的 next 指向原来索引为 n 处的 node; 而原 m 处 Node 的 next 指向 原来 n 处 Node 的 next

链表反转类题目还是画图更直观一些，图片如下：

实现代码如下：

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) {
           return head;
       }
       
       ListNode result = head;
       int pos = 1;

       ListNode preNode = null;
       ListNode tmpNode = head;
       while (pos < m) {
           preNode = tmpNode;
           tmpNode = tmpNode.next;
           pos ++;
       }

       ListNode mHeadNode = tmpNode;
       ListNode mTailNode = null;

       ListNode preTmpNode = tmpNode;
       while (pos <= n) {
           pos ++;
           
           // 记录 n 节点
           mTailNode = tmpNode;
           
           ListNode next = tmpNode.next;
           tmpNode.next = preTmpNode;
           preTmpNode = tmpNode;
           tmpNode = next;
       }
       mHeadNode.next = tmpNode;

       if (preNode == null) {
        return mTailNode;
       }else {
           preNode.next = mTailNode;
           return result;
       }
    }
}

运行结果为 Runtime: 0 ms, faster than 100.00%，代码性能没啥问题。

三. 做题后记

对于反转链表类的题目，最大的问题始终是反转过程中各个指针的指向很容易搞混，画图是解决此类问题的不二法门，把反转过程画出来搞清楚了代码就不难写了。

我是 AhriJ邹同学，前后端、小程序、DevOps 都搞的炸栈工程师。博客持续更新，欢迎小伙伴关注或与我私信交流，互相学习，共同进步。