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.
大清早起来就被链表虐哭了啊， 看了下别人的，额原来可以这么简单，果然脑子还是转不过来的，实际上是很常见的一个题目，代码很简单，完全不用注释也可以的：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode* reverseBetween(ListNode* head, int m, int n) {12 if(head == NULL) return NULL;13 ListNode * p = head;14 int i, j;15 for(i = 1; i < m; ++i){16 p = p->next;17 }18 ListNode * q = p;19 for(i = m; i < n; ++i){20 for(j = i; j < n; ++j){21 q = q->next;22 }23 swap(p->val, q->val);24 n--;25 p = p->next;26 q = p;27 }28 return head;29 }30 }; 注意一下那个swap， swap用的很巧妙。
之后有看到一个大神写出来的，也很简单，贴出来学习一个：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *reverseBetween(ListNode *head, int m, int n) {12 // Start typing your C/C++ solution below13 // DO NOT write int main() function14 if (head == NULL)15 return NULL;16 17 ListNode *q = NULL;18 ListNode *p = head;19 for(int i = 0; i < m - 1; i++)20 {21 q = p;22 p = p->next;23 }24 25 ListNode *end = p;26 ListNode *pPre = p;27 p = p->next;28 for(int i = m + 1; i <= n; i++)29 {30 ListNode *pNext = p->next;31 32 p->next = pPre;33 pPre = p;34 p = pNext;35 }36 37 end->next = p;38 if (q)39 q->next = pPre;40 else41 head = pPre;42 43 return head;44 }45 }; 唉唉，经常遇到链表脑子就转不过来，这个还是要多练练啊。
下面贴一个java版本的,方法基本上和第一种差不多,熟悉一下用法：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution {10 public ListNode reverseBetween(ListNode head, int m, int n) {11 int count = 1;12 ListNode helper = new ListNode(-1);13 helper.next = head;14 ListNode p = helper.next;15 ListNode pPre = helper;16 while(count != m){17 p = p.next;18 pPre = pPre.next;19 count++;20 }21 ListNode midPre = pPre;//第一个节点的位置22 ListNode tmp = null;23 while(count != n){24 tmp = p.next;25 p.next = pPre;26 pPre = p;27 p = tmp;28 count++;29 }30 // ListNode mid2= p; // 指向第二个节点的位置31 tmp = p.next;32 p.next = pPre;33 midPre.next.next = tmp;34 midPre.next = p;35 return helper.next;36 }37 }