题目描述
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example1:
Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL
解题思路
- 先往前走 m - 1 步，这样即为要翻转头结点的前一个
- 采用插入法，这个过程中 pre，cur的指针是不变的，改变的只是next
- 经过1次转换后 得到 1(pre) -> 3(t) -> 2(cur) -> 4
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(m > n){
return NULL;
}
// 这里头指针可能出现翻转 需要重新定义头指针
ListNode* pHead = new ListNode(-1);
ListNode* preNode = pHead;
preNode -> next = head;
int step = m - 1;
while(step > 0 && preNode != NULL){
preNode = preNode -> next;
step--;
}
ListNode* cur = preNode -> next;
// 采用的是插入法
// 第一次插入是 1 -> 3 -> 2 -> 4 -> 5
// 第二次插入是 1 -> 4 -> 3 -> 2 -> 5
// 这期间 cur，pre的是不变的
// pre一直指向的是1， cur一直指向的是2
for(int i = m; i < n; i++){
ListNode* t = cur -> next;
cur -> next = t -> next;
t -> next = preNode -> next;
preNode -> next = t;
}
// 最后返回新生成的头指针的下一个节点即可
return pHead -> next;
}
};
