LeetCode 92. Reverse Linked List II
题目描述
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解法一
解题思路
- 用四个指针分别指向第 $(m - 1)$、$m$、$n$、$(n + 1)$ 个元素
- 从第 $m$ 个元素到第 $n$ 个元素断链，将其逆置，得到新链表
newLink（设置头结点以便操作）
- 再将原链表衔接起来
代码实现
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
|
struct ListNode* t = NULL;
struct ListNode* reverse(struct ListNode* head) {
struct ListNode *L = malloc(sizeof(struct ListNode)), *p;
L->next = NULL;
while(head != NULL){
p = head->next;
head->next = L->next;
L->next = head;
head = p;
}
return L->next;
}
struct ListNode* reverseBetween(struct ListNode* head, int m, int n){
if(!head || m > n)
return head;
struct ListNode *H = malloc(sizeof(struct ListNode));
H->next = head;
struct ListNode *start = H, *end = H, *preStart = start, *rearEnd = end;
int i = 0;
while(i < n) {
if(i < m) {
preStart = start;
start = start->next;
}
end = end->next;
i++;
}
rearEnd = end->next;
end->next = NULL;
t = start;
preStart->next = reverse(start);
t->next = rearEnd;
return H->next;
}
|
解法二
解题思路
实现思路 ：以1->2->3->4->5, m = 2, n=4 为例:
- 定位到要反转部分的头节点 2，head = 2；前驱结点 1，pre = 1；
- 当前节点的下一个节点3调整为前驱节点的下一个节点 1->3->2->4->5,
- 当前结点仍为2， 前驱结点依然是1，重复上一步操作。。。
- 1->4->3->2->5.
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
struct ListNode* reverseBetween(struct ListNode* head, int m, int n){
struct ListNode* dummy = malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode* pre = dummy, *nxt = NULL;
for(int i = 1; i < m; i++)
pre = pre->next;
head = pre->next;
for(int i = m; i < n; i++){
nxt = head->next;
head->next = nxt->next;
nxt->next = pre->next;
pre->next = nxt;
}
return dummy->next;
}
|
