Leetcode系列之链表（5）

题目5：

将一个链表m位置到n位置之间的区间反转，要求使用原地算法，并且在一次扫描之内完成反转。

例如：

给出的链表为1->2->3->4->5->NULL, m = 2 ，n = 4,

返回1->4->3->2->5->NULL.

注意：

给出的m，n满足以下条件：

1 ≤ m ≤ n ≤ 链表长度

思路：

1.先考虑普通的整条链表的翻转（链表翻转）

明确基本数据类型与引用数据类型的区别（请牢记一个链表中的一个节点模型：入口地址，对象，下一个地址）

ListNode t=head.next这种写法改变的是地址并不是拷贝整个对象，如图的模型

利用一个中间变量节点，逐个翻转地址（记住，是地址，操作和变换的都是：入口地址和下一个的地址）

2.考虑截取m到n时翻转的不同

m节点不是原链表的头时，m节点的入口不用置null

n节点不是原链表末尾时，要接上在原链表的位置

代码：

/**

* Definition for singly-linked list.

* public class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) {

*        val = x;

*        next = null;

*    }

* }

*/

public class Solution {

    public ListNode reverseBetween(ListNode head, int m, int n) {

        ListNode orignalPre = new ListNode(0);

        orignalPre.next = head;

        ListNode pre = orignalPre;

        for (int i = 0; i < m - 1; i++) {

            pre = pre.next;

        }

        ListNode cur = pre.next;

        for (int i = m; i < n; i++) {

            ListNode t = cur.next;

            cur.next = t.next;

            t.next = pre.next;

            pre.next = t;

        }

        return orignalPre.next;

    }

}