反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1-2-3-4-5-NULL, m = 2, n = 4 输出: 1-4-3-2-5-NULL
题目分析
- 反转一段区域，首先肯定想到是一个一个反转 比如2-3-4 先3插前面去 3-2-4
，然后4插前面去 4-3-2
- 怎么移过去呢？观察这个局部链表，可以知道我们每次把要处理的插入到链表头即可。
- 因此保留一个pre指向反转区域头部，例如示例中是1
- 遍历反转区域元素current，令temp=current-next保存下位，处理好current的前后指向关系，然后把temp插入到链表头，即pre-next即可。
题解代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* 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个数
{
pre=pre-next;
count++;
}
current=pre-next;//current指向当前处理数
while(count<n)//count计数位，每次将current-next插入到pre-next，相当于利用pre做了个栈，[1,2,3,4,5]为例 current=2 pre=1
{
temp=current-next;//保留current后节点，temp=3
current-next=temp-next;//2-next=4
temp-next=pre-next;//逆转temp和current的前后关系。3-next=2
pre-next=temp;//更新pre的后节点，1-next=3
//current
count++;//完成[1,3,2,4,5]
}
return First.next;
}
};
|