LeetCode:Reverse Linked List II

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节点，从节点m到n依次反转指针，然后把翻转后的串连起来即可本文地址

 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         // IMPORTANT: Please reset any member data you declared, as
13         // the same Solution instance will be reused for each test case.
14         if(head == NULL)return NULL;
15         //为了操作方便，添加额外的头结点tmpHead
16         ListNode *tmpHead = new ListNode(0), *p = head, *mpre = tmpHead;
17         tmpHead->next = head;
18         for(int i = 1; i < m; i++)
19         {mpre = p; p = p->next;}//找到m节点
20         ListNode *pafter = p->next, *mbackup = p;
21         for(int i = 1; i <= n-m; i++)
22         {//反转m到n的指针
23             ListNode *pre = p;
24             p = pafter;
25             pafter = pafter->next;
26             p->next = pre;
27         }
28         //连接
29         mbackup->next = pafter;
30         mpre->next = p;
31         head = tmpHead->next;
32         delete tmpHead;
33         return head;
34     }
35 };