LeetCode面试题：反转链表 II

　　1.简述：

　　给你单链表的头指针head和两个整数left和right，其中left <= right。请将链表节点从位置left反转到位置right，并在反转后返回链表。

　　示例 1：

输入：head = [1，2，3，4，5]， left = 2, right = 4输出：[1，4，3，2，5]

　　示例 2： 输入：head = [5], left = 1, right = 1输出：[5]

　　2.实现代码： class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 因为头节点可能会改变，使用虚拟头节点可以避免复杂的分类讨论 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; // 第 1 步骤：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点 // 建议写在 for 循环里，语义清晰 for (int i = 0; i < left - 1; i++) { pre = pre.next; } // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点 ListNode rightNode = pre; for (int i = 0; i < right - left + 1; i++) { rightNode = rightNode.next; } // 第 3 步骤:切断子链表(截取链表) ListNode leftNode = pre.next; ListNode curr = rightNode.next; // 注：切断链接 pre.next = null; rightNode.next = null; // 第 4 步：同第 206 题，反转链表的子区间 reverseLinkedList(leftNode); // 第 5 步骤：回到原链表 pre.next = rightNode; leftNode.next = curr; return dummyNode.next; } private void reverseLinkedList(ListNode head) { // 也可以使用递归反转链表 ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } }}