题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例1：
1 -> 2 -> 3 -> 4 -> 5
—->
5 -> 4 -> 3 -> 2 -> 1
输入：head = [1，2，3，4，5]
输出：[5，4，3，2，1]
示例2：
1 -> 2
—->
2 -> 1
输入：head = [1，2]
输出：[2，1]
示例3：
输入：head = [ ]
输出：[ ]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
题解1
迭代法，记录pre节点和cur节点，不断交换pre和cur，同时cur后移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
|
题解2
递归法，假设链表其余部分已被反转，怎么去反转它前面的部分。
假设a->b->c->d->e->f->NULL；
若e->f已经被反转成e<-f，此时在d，我们希望将d->e变为d<-e，所以d->next->next=d；
这时d和e互相指向，要断开，所以d->next=NULL。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};
|
题目
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例1：
1 -> 2 -> 3 -> 4 -> 5
—->
1 -> 4 -> 3 -> 2 -> 5
输入：head = [1，2，3，4，5], left = 2, right = 4
输出：[1，4，3，2，5]
示例2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
题解
首先，凡是链表题都可以创建个伪头节点，如下
1
2
| ListNode* dummy = new ListNode(0);
dummy->next = head;
|
参考反转链表，这题是特定位置反转，可以根据left和right取出需要反转的链表，代入反转链表的解法进行反转，再和前后链表拼接。
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
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* end = dummy;
for (int i = 0; i < left - 1; i++)
pre = pre->next;
ListNode* start = pre->next;
for (int i = 0; i < right; i++)
end = end->next;
ListNode* next = end->next;
end->next = NULL;
pre->next = reverseList(start);
start->next = next;
return dummy->next;
}
};
|
题目
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例1：
1 -> 2 -> 3 -> 4 -> 5
—->
2 -> 1 -> 4 -> 3 -> 5
输入：head = [1，2，3，4，5], k = 2
输出：[2，1，4，3，5]
示例2：
1 -> 2 -> 3 -> 4 -> 5
—->
3 -> 2 -> 1 -> 4 -> 5
输入：head = [1，2，3，4，5], k = 3
输出：[3，2，1，4，5]
示例3：
输入：head = [ ]
输出：[ ]
提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
题解
参考反转链表Ⅱ，反转链表Ⅱ中是给定left和right进行截取来反转，这里可以通过遍历给定的链表，每k个截取一段链表，然后反转并拼接
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
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur != NULL) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* end = dummy;
while (end->next != NULL) {
ListNode* start = pre->next;
for (int i = 0; i < k && end != NULL; i++)
end = end->next;
if (end == NULL)
break;
ListNode* next = end->next;
end->next = NULL;
pre->next = reverseList(start);
start->next = next;
pre = start;
end = pre;
}
return dummy->next;
}
};
|
