- Reverse Linked List II:题目链接
方法1：穿针引线
- pre:指向[m, n]这段链表之前的一个节点
- curNode: 当前指向的节点 简称c
- nextNode: 当前指向的下一个节点 简称n
基本思想：先找到m节点的前驱pre所在的位置，每次将curNode放在nextNode的后面，将nextNode放在pre的后面 如下所示1
2
3
4
5
6
7
8
9
10
11
12m = 2， n = 4 将[m,n]的元素逆转
初始： dummyHead --> 1 --> 2 --> 3 --> 4 --> 5
pre c n
一次： dummyHead --> 1 --> 3 --> 2 --> 4 --> 5
pre c n
二次： dummyHead --> 1 --> 4 --> 3 --> 2 --> 5
pre c n
// 注意在这里我只需要提前遍历一趟链表找到m前驱的位置并不需要找去n的位置，进而找到m的位置然后在做n-m次图示操作就行
AC代码: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// 时间复杂度O(N) 空间复杂度O(1)
struct ListNode *reverseBetween(struct ListNode *head, int m, int n) {
// 假设：1 -> 2 -> 3 -> 4 -> 5 m = 1, n = 2 不设头结点 要找到1的前驱 pre只能从head开始
// 不能等于null否则pre->next无效，无法后移 即 pre = 1 、start = 1 、 end = 2
// 为了在m=1时统一操作就跟单链表的插入删除一样 加上头结点
struct ListNode *dummyHead = (struct ListNode *) malloc(sizeof(struct ListNode));
dummyHead->next = head;
if(m == n){
return head;
}
struct ListNode *pre = dummyHead, *curNode = NULL, *nextNode = NULL;
int i = 0;
while (pre != NULL && i < m - 1) { // 找到pre的位置
pre = pre->next;
i++;
}
if (NULL == pre) {
return NULL;
}
curNode = pre->next; // 确定curNode的位置
for (i = 0; i < n - m && curNode != NULL; ++i) { // 开始reverse
printf("aaaa\n");
nextNode = curNode->next;
curNode->next = nextNode->next;
nextNode->next = pre->next; // 注意这里不要写成了nextNode>next = curNode
pre->next = nextNode;
}
return dummyHead->next;
}
pS:源代码链接