题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解题思路
本题类似于反转链表的做法，但不同的是只反转中间的一段节点，所以在反转完一段链表后，应重新拼接到原链表对应位置中间。具体步骤为：
- 首先找到反转链表的首尾节点，若首节点不是链表头结点，还要同时保存首节点的前一个节点，以便反转完后的拼接
- 然后按照反转链表的做法维护三个指针，从头到尾一遍遍历调整指针，这样遍历到尾节点时正好反转完指定链表段
- 最后将原来的首节点next指针指向段后节点，若首节点不是链表头结点，还要讲首节点前一个节点的next指针指向原来的尾节点
代码
/**
* 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) {
ListNode *left = head, *first, *pre;
int step = m;
while(step - > ){
left = left->next;
step--;
}
if(m > ) first = pre = left->next;
else first = pre = head;
step = n - m;
if(step > ){
ListNode *now = pre->next;
ListNode *next = now->next;
while(step-- > ){
now->next = pre;
pre = now;
now = next;
if(next) next = now->next;
}
if(m > ) left->next = pre;
first->next = now;
}
if(m > ) return head;
else return pre;
}
};