題目
反轉(zhuǎn)從位置 m 到 n 的鏈表悴品。請(qǐng)使用一趟掃描完成反轉(zhuǎn)谨设。
說明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
思路
參考簡(jiǎn)書用戶安全地帶的解法http://www.reibang.com/p/fbe6012c9e52
#include <cstddef>
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 (head == NULL) return NULL;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* previous = dummy;
for (int i = 0; i < m - 1; i++)
{
previous = previous->next;
}
ListNode* current = previous->next;
ListNode* post = current->next;
for (int i = 0; i < n - m; i++)
{
current->next = post->next;
post->next = previous->next;
previous->next = post;
post = current->next;
}
return dummy->next;
}
};
