【LeetCode-面试算法经典-Java实现】【092-Reverse Linked List II（反转单链表II）】
分类：LeetCode
【092-Reverse Linked List II（反转单链表II）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
题目大意
给定一个单链表，将第m到第n个之间的元素进行转。 给定的n和m都是合法的，使用原地方法进行解决（使用常量辅助空间）
解题思路
先找到第一个要反转的元素的前驱（prev），再计算要进行反转的元素个数，对元素进行头插法，插在prev后面，，同时保持链表不断开。
代码实现
链表结点类
public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}
算法实现类
public class Solution {public ListNode reverseBetween(ListNode head, int m, int n) {ListNode root = new ListNode(0);ListNode p = root;root.next = head;for (int i = 1; i < m && p != null; i++) {p = p.next;}if (p != null) {ListNode q = p.next;ListNode r;// 如果m为负数就认为是从第一个开始交换if (m < 1) {m = 1;}n = n – m + (int i = 1; i < n && q.next != null ; i++) {// 为要进行尾插的结点r = q.next;// 在q结点的后面进行尾插操作 q.next = r.next;r.next = p.next;p.next = r;}head = root.next;}return head;}}评测结果
点击图片，鼠标不释放，拖动一段位置，释放后在新的窗口中查看完整图片。
特别说明欢迎转载，转载请注明出处【】
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇【LeetCode-面试算法经典-Java实现】【089-Gray Code（格雷码）】下一篇【LeetCode-面试算法经典-Java实现】【094-Binary Tree Inorder Traversal（二叉树中序遍历）】
顶2踩0
没有什么可留恋，只有抑制不住的梦想，
