题目：
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given1->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; }}
三刷:
方法和二刷一样。
- 先找到m的前一个节点pre，这里要注意是在m > 1的条件下进行遍历
- 设置head = pre.next，用来进行遍历， 设置tail = head，因为翻转完毕以后这个head节点应该处于最后，所以我们设置这个tail用来连接n后面的节点们
- 设置tmp = head，也可以直接设置tmp为null，用来保存时head下一位置的节点
- 设置pre.next = null
- 在n > 0的情况下进行翻转，每次n--
- 最后连接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