- 0. Leetcode [1290. 二进制链表转整数](https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer/)
- 分析与解答
- 1. Leetcode [237. 删除链表中的节点](https://leetcode.cn/problems/delete-node-in-a-linked-list/)
- 分析与解答
- 2. Leetcode [剑指 Offer II 024. 反转链表](https://leetcode.cn/problems/UHnkqh/)
- 分析与解答
- 3. Leetcode [1019. 链表中的下一个更大节点](https://leetcode.cn/problems/next-greater-node-in-linked-list/)
- 分析与解答
- 总结
分析与解答给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
本题只要遍历链表，按照题意将了每个节点的值放在结果的相应位上即可：
class Solution {
public:
int getDecimalValue(ListNode* head) {
int result(0);
while (head != nullptr) { // 遍历链表
result = (result << 1) | head->val; // 更新相应值
head = head->next;
}
return result;
}
};
算法时间复杂度为 O ( N ) O(N) O(N)
1. Leetcode 237. 删除链表中的节点分析与解答请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
所以到底为什么没有头节点呢？单向链表没有前一个节点要怎么删除呢…没错，不需要对节点进行操作，直接对节点中的值进行操作也能实现_删除_的效果。
从给出的节点往后搜索全部节点，将节点中的值依次往前赋值，达到删除的效果。需要注意的是，在删除最后一个节点时，要将前一个节点的 next 置为 nullptr：
class Solution {
public:
void deleteNode(ListNode* node) {
while (node->next != nullptr) {
node->val = node->next->val;
if (node->next->next == nullptr) { // 删除尾节点
node->next = nullptr;
break;
}
node = node->next;
}
}
};
算法时间复杂度为 O ( N ) O(N) O(N)
2. Leetcode 剑指 Offer II 024. 反转链表分析与解答给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
据说本题面试常考哦~首先是一种不好的方式（好长时间不用链表，第一时间想到的只是这个…），遍历链表后重新构造一个反向链表：
// 取出所有值后再构造链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
vector numInList;
ListNode* cur(head);
while (cur != nullptr) {
numInList.push_back(cur->val);
cur = cur->next;
}
ListNode* result(nullptr);
for (int i = numInList.size() - 1; i >= 0; --i) {
if (result == nullptr) { // 链表中第一个节点
result = new ListNode(numInList[i]);
cur = result;
} else {
ListNode* curNode = new ListNode(numInList[i]);
cur->next = curNode;
cur = cur->next;
}
}
return result;
}
};
算法时间复杂度为
O
(
N
)
O(N)
O(N)。虽然过了，但是这题有更加链表的方式：
对于单向链表操作，最怕破坏节点间的关系后无法正常索引后续节点。但只要使用一个指针指向当前节点的下一个节点，这样在更改当前节点的 next 后就不怕无法继续索引了：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* curNode(head); // 当前操作的节点
ListNode* preNode(nullptr); // 逆序后当前节点要指向的下一个节点
while (curNode) {
// 正序时当前节点的下一个节点，防止破坏索引关系后无法找到
ListNode* nextNode = curNode->next;
curNode->next = preNode; // 构造逆序链表
preNode = curNode; // 更新
curNode = nextNode;
}
return preNode;
}
};
算法时间复杂度为 O ( N ) O(N) O(N)
3. Leetcode 1019. 链表中的下一个更大节点分析与解答给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
本题涉及单调栈，当链表中下一个元素小于等于栈顶元素时，将当前元素放入栈中；若下一个元素大于栈顶元素，则将栈顶元素弹出，并更新相应元素的 answer[i]，直至栈顶元素大于下一个元素。这里栈中需要存放节点值与节点下标，因此使用 std::pair
class Solution {
public:
vector nextLargerNodes(ListNode* head) {
vector result;
int resultTmp[10000];
stack st;
stack stIdx; // 下标栈，与 st 同时更新
ListNode* cur(head);
int idx(0);
while (cur != nullptr) {
// 当前数字比栈顶小，push
// 注意这里用了逻辑运算符短路确保 .top() 不抛出异常
if (st.size() == 0 || cur->val <= st.top()) {
st.push(cur->val);
stIdx.push(idx++);
} else {
// 弹出栈中所有元素并更新 result
while (st.size() > 0 && st.top() < cur->val) {
st.pop();
int id = stIdx.top();
stIdx.pop();
// result.push_back(cur->val);
resultTmp[id] = cur->val;
}
// 放入当前元素
st.push(cur->val);
stIdx.push(idx++);
}
cur = cur->next;
}
while (st.size() > 0) {
st.pop();
int id = stIdx.top();
stIdx.pop();
resultTmp[id] = 0;
}
for (int i = 0; i < idx; ++i) { // 将结果放入 vector 中
result.push_back(resultTmp[i]);
}
return result;
}
};
下面是使用 std::pair 的方式：
class Solution {
public:
vector nextLargerNodes(ListNode* head) {
stack> sk; // std::pair<> 存放两个元素
vector result;
int idx(0);
while (head) {
result.push_back(0); // 每有一个元素 push 一次，代码简洁，但元素多时会多次重新分配内存，降低效率
if (sk.size() == 0 || std::get<0>(sk.top()) >= head->val) {
;
} else { // 弹出栈顶元素
while (sk.size() > 0 && std::get<0>(sk.top()) < head->val) {
auto a = sk.top();
result[std::get<1>(a)] = head->val;
sk.pop();
}
}
sk.push(std::make_pair(head->val, idx++));
head = head->next;
}
return result;
}
};
总结
许久不用链表让很多指针做法都有些忘记了，但是想起来后还是发现链表是一种很有魅力的数据结构，能够通过指针操作做到很多很酷的事情。
