关于java:反转链表-II

反转链表 II LeetCode 92

本文浏览前置条件：

已理解 反转链表 leetcode 206 题
起源：力扣（LeetCode）
https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

原题：
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

另一种输出条件：
初始状况：
1 <= m <= n <= 链表长度
输出：head = [1,2,3,4,5], m = 2, n = 4
输入：[1,4,3,2,5]

题解:

此题为单向链表反转的变形题。

咱们只需反转区间链表，而后拼接上反转之前左半局部，反转前右半局部.
那么咱们须要找到，反转区间的前一个节点，反转区间后一个节点，反转后的头节点，以及反转后的尾节点，把他们三个从新拼接成一个链表即可。

已知：1 <= m <= n <= 链表长度 (length)，反转 m,n 之间的链表
设：start 为链表头地位，end 为尾部，mid 为两头某一个节点
m,n 整体情况可分为以下几种状况

• m = start, n = end (1, length) 头尾反转（全副反转）
• m = start, n = mid (1,5) 头中反转 (区间翻转)
• m = mid1, n = mid2 (2,4) 中部区间反转 (区间翻转)
• m = mid, n = end (2, length) 中尾区间反转 (区间翻转)

代码中：
leftNode 反转前，反转链表的前一个节点
reversedTailNode 反转链表的尾结点
pre 反转链表的头节点
cur 反转链表的下一个节点, 既反转区间的后一个节点

那么当

• start, end ; head = pre, tail+cur (此时 cur==null, 无需解决)
• start, mid ; head = pre, tail+cur
• mind1, mind2; left+pre, tail+cur
• mind, end ; left+pre, tail+cur (此时 cur==null, 无需解决)
  最初返回 head 既可。

由上思路，代码为：

public Node reversList2(Node head, int m, int n) {if (head == null) {return null;}
    if (m >= n) {return head;}

    Node leftNode = head;
    Node reversedTailNode = head;
    Node cur = null;
    Node pre = null;
    // 找到反转起始地位
    if (m == 1) {cur = leftNode;} else {for (int i = 1; i < m - 1; i++) {leftNode = leftNode.next;}
      cur = leftNode.next;
      reversedTailNode = cur;
    }
    int offset = n - m + 1;
    while (cur != null && offset > 0) {
      offset--;
      Node next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    // 拼接反转后的左半局部
    if (leftNode != reversedTailNode) {leftNode.next = pre;} else {head = pre;}
    // 拼接反转后的右半局部
    reversedTailNode.next = cur;
    return head;
  }