LeetCode题解-92. 反转链表 II

题目描述

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

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

示例:

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

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

思路

如题意，反转位置m到n的链表，然后将第m-1个节点连接到反转后链表的头节点，将反转后链表的尾节点连接原链表的第n+1个节点。

代码

    public static ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode m_1Node = dummy;
    // 记录下第m-1个节点，因为反转后，需要把这个节点和反转后的那个链表的表头连接起来
    for (int i = 0; i < m - 1; i++) {
        m_1Node = m_1Node.next;
    }
    // tempNode是第m个节点，也是反转后链表的尾节点
    ListNode tempNode = m_1Node.next;
    ListNode prev = null;
    ListNode next = null;
    ListNode mNode = m_1Node.next;
    // 反转m到n这段链表，经过这段循环后，mNode节点就是第n+1个节点
    for (int i = 0; i <= n - m; i++) {
        next = mNode.next;
        mNode.next = prev;
        prev = mNode;
        mNode = next;
    }
    // 连接第m-1个节点和反转后链表的头节点
    m_1Node.next = prev;
    // 连接反转后链表的尾节点和第n+1个节点
    tempNode.next = mNode;
    return dummy.next;
}