题目概要
将指定范围内的链表翻转。
题目链接
题目解析
注意，题目中标注了条件：$1\le m \le n \le length_of_list$
我们现在来关注翻转某局部链表时，所需要进行的操作：
[+]->[+]->[o]->[o]->[o]->[o]->[o]->[x]->[+]->[+]->^
^ ^ ^
| | |
tail revTail revHead
上图中[+]表示的结点为正常结点，而[o]为已经被翻转过的链表结点，[x]为正在被翻转的结点。
易知此时需要进行的操作如下：
revHead = revTail->next;
revTail->next = revHead->next;
revHead->next = tail->next;
tail->next = revHead;
之后，上述链表将变为如下图所示形式：
[+]->[+]->[x]->[o]->[o]->[o]->[o]->[o]->[+]->[+]->^
^ ^ ^
| | |
tail revHead revTail
如此反复多次，准确的说是$n-m$次后，就可以完成翻转了。
同时还需要注意的是$m==1$的情形。
复杂度分析
时间复杂度：$O(n)$
空间复杂度：$O(1)$
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == NULL || head->next == NULL) return head;
ListNode* newHead = new ListNode(0);
newHead->next = head;
ListNode* tail = newHead;
for (int i=0; i<m-1; ++i)
tail = tail->next;
ListNode* revTail = tail->next;
ListNode* revHead = NULL;
for (int i=0; i<n-m; ++i) {
revHead = revTail->next;
revTail->next = revHead->next;
revHead->next = tail->next;
tail->next = revHead;
}
// delete the pointer
ListNode* toDelete = newHead;
delete toDelete;
newHead = newHead->next;
return newHead;
}
};
广告区域
本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083
