反转链表(二)JAVA

反转列表（二）

题目描述

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

• 说明:

  1 ≤ m ≤ n ≤ 链表长度。

• 示例:

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

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

题解(java)

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {

        // 判断是否为空链表
        if (head == null) {
            return null;
        }

         
        ListNode cur = head;
        ListNode prev = null;
        //把 prev 和 cur移到头断点两侧
        while (m > 1) {
            prev = cur;
            cur = cur.next;
            m--;
            n--;
        }

       //并记为 con 和 tail
        ListNode con = prev, tail = cur;

        // 继续移动 prev 和 cur 到尾断点两侧
        while (n > 0) {
            ListNode third = cur.next;
            cur.next = prev;
            prev = cur;
            cur = third;
            n--;
        }

        // 从新连接
        //要考虑到从第一节点开始反转的情况
        if (con != null) {
            con.next = prev;
        } else {
            head = prev;
        }

        tail.next = cur;
        return head;
    }
}
           

图示

详解

-.简单来说，该题的目的为反转链表中的其中一段节点，那么我们只要分别找到头断点和尾断点两侧的端点，再重新连接这四个端点即可（特殊情况，从第一个节点开始反转）

-1>.首先定义一个空指针 prev 指向 nul，以及指针 cur 指向 head这两个指针一起同步向后移动，直到找到头断点的位置，因为在初始时，cur 正好为 m = 1 处，所以当 m>1 时，两节点开始移动。

• 2>找到位置后，将 con 定位指向 prev，tail 定位指向 cur,在继续顺移直到找到尾断点，其中 prev 和 cur 分别位于尾断点两侧。
• 3>.头断点和尾断点的位置都找到后，因为在移动的过程中，我们已经反转了该部分的链表，所以只需将链表重新连接即可【con 连接 prev, tail 连接 cur】
• 4>.连接完毕后，返回新的链表即可

Tips

• 解释为什么找头断点遍历条件为 m>1 ,找尾断点便利条件为 n>0：因为找头断点时，prev指向的是需反转区间的链表的头结点，找尾断电时，prev指向的是该区间链表尾节点之后的那个节点。
• 注意：有一种特殊情况为链表中的第一个节点也在需反转的范围内，这时只需重新令尾断点前的尾节点为新的头结点，再使 tail 连接 cur 即可得到新的链表
• 注意：在开始操作之前还是要判断该链表是否为空链表。

难点

• 多个指针的复杂操作

声明

• 原作者E.L.E
• <本文章著作权归作者所有，商业转载请获得作者授权，非商业转载请注明出处>
• <欢迎大家评论>