LeetCode 0092 - Reverse Linked List II
# Hints
水题
链表
# 前置题目
LeetCode 0206 - Reverse Linked List
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given the head of a singly linked list and two integers left
and right
where left <= right
, reverse the nodes of the list from position left
to position right
, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Constraints:
The number of nodes in the list is n.
# 题意
给定一个单链表,给定两个整数 和 ,要求将子链表 的顺序翻转。
# 题解
本题是 LeetCode 0206 的简单扩展,我们只需找到 和 对应的节点位置,在翻转子链表之后单独处理边界处的指针即可。
细节问题:
注意特判空链表。
注意特判 的情况。
# AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode * next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode * next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode * reverseBetween(ListNode * head, int left, int right) {
// 特判
if (head == nullptr) {
return head;
}
// 初始化
ListNode * prv = nullptr;
ListNode * cur = head;
int idx = 0;
// 获取边界
while (cur != nullptr && idx < left - 1) {
prv = cur;
cur = cur->next;
idx ++;
}
ListNode * xprv = prv;
ListNode * xcur = cur;
// 遍历
while (cur != nullptr && idx < right) {
ListNode * nxt = cur->next;
cur->next = prv;
prv = cur;
cur = nxt;
idx ++;
}
// 处理边界
if (xprv != nullptr) {
xprv->next = prv;
} else {
head = prv;
}
xcur->next = cur;
// 返回
return head;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01