反转链表 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; }