Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
这道题的要求是将链表中m到n位置反转。
链表处理，先加一个空表头，便于处理。然后令l指针移动到m位置前面，令r移动到m位置，这样不断把r后面的节点插入到l后面，直到n位置。
假设m=2，n=4，链表为：
head -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
加头之后为：
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
令l指针移动到m位置前面，令r移动到m位置，即：
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
^ ^
| |
l r
r后面的节点插入到l后面：
ListNode *temp = l -> next:
h -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
^ ^
| |
l temp、r
l -> next = r -> next:
|-------->|
h -> 0 -> 1 2 -> 3 -> 4 -> 5 -> NULL
^ ^
| |
l temp、r
r -> next = r -> next -> next:
|-------->|
h -> 0 -> 1 2 3 -> 4 -> 5 -> NULL
^ |-------->|
| ^
l |
temp、r
l -> next -> next = temp:
|-------->|
h -> 0 -> 1 2 <- 3 4 -> 5 -> NULL
^ |-------->|
| ^
l |
temp、r
即：
h -> 0 -> 1 -> 3 -> 2 -> 4 -> 5 -> NULL
^ ^
| |
l r
进而继续把r后面节点插入到l后面，以此类推，进行循环。。。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
ListNode *reverseBetween(ListNode *head, int m, int n)
{
ListNode *h = new ListNode(0);
h -> next = head;
ListNode *l = h, *r;
for(int i = 1; i < m; ++ i)
l = l -> next;
r = l -> next;
for(int i = 1; i < n - m + 1; ++ i)
{
ListNode *temp = l -> next;
l -> next = r -> next;
r -> next = r -> next -> next;
l -> next -> next = temp;
}
return h -> next;
}
};