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.

链表的操作,不难,就是比较繁琐,在纸上先画出操作步骤理清思路。

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
41
42
43
44
45
46
47
48
49
50
51
52
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseLinklist(ListNode* head) {
ListNode *p1 = head, *p2 = head->next, *tmp;
while (p2) {
tmp = p2->next;
p2->next = p1;
p1 = p2;
p2 = tmp;
}
head->next = nullptr;
return p1;
}

ListNode* reverseBetween(ListNode* head, int m, int n) {
if (head == nullptr || head->next == nullptr || m == n)
return head;
ListNode *p1 = head, *dummy = new ListNode(-1), *p2 = dummy, *p3, *p4, *p5;
dummy->next = head;
int i = 1;
while (p1) {
if (i == m && p2) {
p2->next = nullptr;
p3 = p1;
} else if (i < m) {
p2 = p1;
}

if (i == n) {
p4 = p1->next;
p1->next = nullptr;
break;
}

p1 = p1->next;
i++;
}

p5 = reverseLinklist(p3);
p2->next = p5;
p3->next = p4;
return dummy->next;
}
};