题目：

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.

链接：  

题解：

把翻转部分隔离出来，记录这部分之前的节点和之后的节点。然后翻转这部分，再和之前记录的两个节点连接起来就可以了。

Time Complexity - O(n)， Space Complexity - O(1)

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode reverseBetween(ListNode head, int m, int n) {        if(head == null || head.next == null || m == n)            return head;        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode preHeadToReverse = dummy, tailToReverse = dummy;        int count = 0;                while(count < n) {            if(tailToReverse == null)                return dummy.next;            if(count < m - 1)                preHeadToReverse = preHeadToReverse.next;            tailToReverse = tailToReverse.next;            count++;        }                ListNode headToReverse = preHeadToReverse.next, postTailToReverse = tailToReverse.next;        tailToReverse.next = null;        preHeadToReverse.next = reverse(headToReverse);        headToReverse.next = postTailToReverse;        return dummy.next;    }        private ListNode reverse(ListNode head) {        if(head == null || head.next == null)            return head;        ListNode dummy = new ListNode(-1);                while(head != null) {            ListNode tmp = head.next;            head.next = dummy.next;            dummy.next = head;            head = tmp;        }                return dummy.next;    }}

这道题目应该和其他几道联合起来做，比如按照先后顺序完成以下几道题目

1) Reverse Linked List

2) Reverse Linked List II

3) Swap Node in Pairs

4) Swap Node in K-Gruo

 

二刷：

我们需要记录四个变量， pre， headToReverse，tailToReverse， postTail，然后当遍历时节点在headToReverse以及tailToReverse的时候我们反转。下面我写得比较麻烦，单独把reverse写成了一个函数，而切要先找到结尾点才能reverse，这样就多遍历了一遍反转区域，还需要好好改写。

Java:

Time Complexity - O(n)， Space Complexity - O(1)

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode reverseBetween(ListNode head, int m, int n) {        if (head == null || head.next == null || m == n) {            return head;        }        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode preHeadToReverse = dummy, tailToReverse = dummy;        while (m > 1 || n > 0) {            if (m > 1) {                preHeadToReverse = preHeadToReverse.next;                m--;            }            if (n > 0) {                tailToReverse = tailToReverse.next;                n--;            }        }        ListNode headToReverse = preHeadToReverse.next, postTailToReverse = tailToReverse.next;        tailToReverse.next = null;        preHeadToReverse.next = reverse(headToReverse);         headToReverse.next = postTailToReverse;        return dummy.next;    }        private ListNode reverse(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode dummy = new ListNode(-1);         ListNode tmp = new ListNode (-1);        while (head != null) {            tmp = head.next;            head.next = dummy.next;            dummy.next = head;            head = tmp;        }        return dummy.next;    }}

 

下面直接one pass。 我们先设置fakeHead dummy， 让preHead = dummy， 找的过程中当m > 1的时候  preHeadToReverse = preHeadToReverse .next， 然后找到headToReverse = preHeadToReverse.next，也设置一个标记tail = headToReverse，最后用来添加连接反转前节点n的后一个节点postTail。

接下来我们先设置preHeadToReverse.next = null，在(n > 0以及headToReverse != null)的情况下， 我们利用reverse linkedlist的方法遍历这部分反转区域。遍历完毕以后的headToReverse就等于反转前节点n的下一个节点postTail， 这时候我们只需要将两部分连接起来，做一个  tail.next = headToReverse就可以了。还能再简化。

 

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode reverseBetween(ListNode head, int m, int n) {        if (head == null || head.next == null || m == n) {            return head;        }        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode preHeadToReverse = dummy;        while (m > 1) {            preHeadToReverse = preHeadToReverse.next;            m--;            n--;        }        ListNode headToReverse = preHeadToReverse.next;        ListNode tail = headToReverse, node = headToReverse;        preHeadToReverse.next = null;        while (n > 0 && headToReverse != null) {            node = headToReverse.next;            headToReverse.next = preHeadToReverse.next;            preHeadToReverse.next = headToReverse;            headToReverse = node;            n--;        }        tail.next = headToReverse;        return dummy.next;    }}

 

三刷:

方法和二刷一样。

1. 先找到m的前一个节点pre，这里要注意是在m > 1的条件下进行遍历
2. 设置head = pre.next，用来进行遍历，  设置tail = head，因为翻转完毕以后这个head节点应该处于最后，所以我们设置这个tail用来连接n后面的节点们
3. 设置tmp = head，也可以直接设置tmp为null，用来保存时head下一位置的节点
4. 设置pre.next = null
5. 在n > 0的情况下进行翻转，每次n--
6. 最后连接tail和tmp，然后返回结果

Java:

/** * Definition for singly-linked list. * 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 dummy = new ListNode(-1);        dummy.next = head;        ListNode pre = dummy;                while (m > 1) {                 pre = pre.next;            m--;            n--;        }                head = pre.next;        ListNode tail = head;        ListNode tmp = head;        pre.next = null;                while (n > 0) {            tmp = head.next;            head.next = pre.next;            pre.next = head;            head = tmp;            n--;        }                tail.next = tmp;        return dummy.next;    }}

 

 

 

Reference:

https://leetcode.com/discuss/10794/share-my-java-code 

https://leetcode.com/discuss/25580/simple-java-solution-with-clear-explanation

https://leetcode.com/discuss/35440/240ms-java-solution

https://leetcode.com/discuss/72660/short-java-solution-for-reverse-linked-list-ii