反轉(zhuǎn)鏈表
反轉(zhuǎn)從位置 m 到 n 的鏈表浸赫。請使用一趟掃描完成反轉(zhuǎn)和橙。
說明:
1 ≤ m ≤ n ≤ 鏈表長度诉探。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
題目分析
- 反轉(zhuǎn)一段區(qū)域沈撞，首先肯定想到是一個一個反轉(zhuǎn)
比如2->3->4 先3插前面去 3->2->4 迄沫，然后4插前面去 4->3->2
- 怎么移過去呢碍脏？觀察這個局部鏈表仿野，可以知道我們每次把要處理的插入到鏈表頭即可塞栅。
- 因此保留一個pre指向反轉(zhuǎn)區(qū)域頭部准潭，例如示例中是1
- 遍歷反轉(zhuǎn)區(qū)域元素current趁俊，令temp=current->next保存下位，處理好current的前后指向關(guān)系刑然，然后把temp插入到鏈表頭寺擂，即pre->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)
{
int count=1;
ListNode* temp;
ListNode* current;
ListNode First(0);
First.next=head;
ListNode* pre=&First;
while(count<m)//pre停在原第m-1個數(shù)
{
pre=pre->next;
count++;
}
current=pre->next;//current指向當前處理數(shù)
while(count<n)//count計數(shù)位泼掠，每次將current->next插入到pre->next怔软，相當于利用pre做了個棧，[1,2,3,4,5]為例 current=2 pre=1
{
temp=current->next;//保留current后節(jié)點武鲁，temp=3
current->next=temp->next;//2->next=4
temp->next=pre->next;//逆轉(zhuǎn)temp和current的前后關(guān)系爽雄。3->next=2
pre->next=temp;//更新pre的后節(jié)點，1->next=3
//current
count++;//完成[1,3,2,4,5]
}
return First.next;
}
};
