- 1.1290. 二进制链表转整数
- 2.237. 删除链表中的节点
- 3.剑指 Offer II 024. 反转链表
- 4.1019. 链表中的下一个更大节点
原题链接
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1：
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：
输入：head = [0]
输出：0
示例 3：
输入：head = [1]
输出：1
示例 4：
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880
示例 5：
输入：head = [0,0]
输出：0
提示：
链表不为空。
链表的结点总数不超过 30。
v每个结点的值不是 0 就是 1。
遍历链表，在遍历的过程中不断对ans进行操作即可。
具体的做法就是我们利用ans的二进制形式，每遍历到一个新的结点，让ans左移一位，并对最后一位按位或上当前结点的值。
比如开始时我们的ans=0,head = [1,0,1],开始时候由于ans=000，所以左移并不影响，接下来按位或上1，ans变成了001，接下来遍历到了head[1]，ans左移一位010，按位或0变成了010，下面遍历到了head[2]，ans左移一位变成了100，按位或变成了101.
class Solution {
public:
int getDecimalValue(ListNode* head) {
int ans=0;
while(head){
ans=(ans<<1|head->val);
head=head->next;
}
return ans;
}
};
2.237. 删除链表中的节点
原题链接
请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。
题目数据保证需要删除的节点 不是末尾节点 。
示例 1：
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
示例 2：
输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9
提示：
链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是 唯一 的
需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点
利用链表的数据结构，我们只需要把当前结点变为他的下一个结点即可。
class Solution {
public:
void deleteNode(ListNode* node) {
node->val=node->next->val;
node->next=node->next->next;
}
};
观察代码我们发现其实我们当前结点的数据并没有真的删除，只是我们无法访问到该节点了。
原题链接
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
介绍两种方法迭代和递归：
迭代的做法就是进行头插，我们不断遍历链表，吧当前结点先在当前链表删除，然后将他头插。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr){
return nullptr;
}
ListNode* prev=new ListNode();//哨兵位方便头插和返回
prev->next=head;
ListNode* cur=head->next;//当前结点
ListNode* pprev=head;//头节点，这里是永远不变的。
while(cur){
pprev->next=cur->next;
//每次遍历先将head指向cur的下一个结点
cur->next=prev->next;
prev->next=cur;
//头插，这里的prev是哨兵位。
//要先把cur的next变为prev的next，再将prev的next变为cur
cur=pprev->next;//移动cur遍历下一个结点
}
return prev->next;
}
};
递归做法：
递归的具体做法就是我们先找到链表的尾结点，由于我们是递归系统是帮我们进行压栈的，所以这里的head在递归结束的时候每层分别是链表的倒序序列。
比如链表为1 - > 2 - > 3 -> 4 - > 5，递归结束每层分别为4 3 2 1，返回值为5.现在我们就将链表进行逆置，也就是把当前节点的下一个结点变为他自己，再将他自己的结点设置为空。这里的ans一直都是原始链表的尾结点，同时也是我们反转后链表的头节点。
具体的过程这里解释一下：
原始 ：1 - > 2 - > 3 -> 4 - > 5
递归结束的第一层 : 1 - > 2 - > 3 - > 4 < - 5 4->null
递归结束的第二层 : 1 - > 2 - > 3 < - 4 < - 5 3->null
递归结束的第三层 : 1 - > 2 < - 3 < - 4 < - 5 2->null
递归结束的第二层 : null < - 1 < - 2 - > 3 < - 4 < - 5
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr||head->next==nullptr)
return head;
ListNode* ans=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return ans;
}
};
4.1019. 链表中的下一个更大节点
原题链接
给定一个长度为 n 的链表 head
对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。
返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
示例 1：
输入：head = [2,1,5]
输出：[5,5,0]
示例 2：
输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]
提示：
链表中节点数为 n
1 <= n <= 10^4
1 <= Node.val <= 10^9
这里我们要找到当前结点之后的第一个比他大的数，同时又注意到如果链表的某个区间是递增的我们可以找到该区间的最大值然后对返回数组中所有当前区间的值变为该最大值。
于是想到了栈，利用栈不断维护最大值，如果当前的结点值大于栈顶元素的值，就让栈顶元素出栈，并且对返回数组中的该位置进行赋值，直到栈顶元素不大于当前元素。也就是说我们的栈中维护的是一个单调递增的序列。
当遍历到链表的最后一个元素的时候，我们再对栈进行操作，此时栈中存储的元素全部为链表中不存在他之后的元素有比它大的元素。我们将他们出
栈并将返回数组中的当前位置设置为0即可。（这里的栈存储的是一个数对，first为下标，seconde为val）
先看代码，在之后会对一个例子进行解释。
class Solution {
public:
vector nextLargerNodes(ListNode* head) {
stack> stk;
int index=0;
vector ans;
for(int i=0;i<10000;++i){
ans.push_back(-1);
}
while(head){
if(stk.empty()){
stk.push({index,head->val});
}else {
while(!stk.empty()&&head->val>stk.top().second){
int idx=stk.top().first;
ans[idx]=head->val;
stk.pop();
}
}
stk.push({index,head->val});
head=head->next;
index++;
}
while(!stk.empty()){
int idx=stk.top().first;
stk.pop();
ans[idx]=0;
}
while(ans.size()>index){
ans.pop_back();
}
return ans;
}
};
比如:head = [2,7,4,3,5]
遍历到2时栈中为[2]，遍历到7比栈顶元素大，所以栈顶出栈并且返回数组设置为[7].之后7入栈，栈为【7】.
遍历到4，栈中不存在比他小的直接入栈，栈为[7,4]，3的时候同理栈为[7,4,3],最后遍历到5，比栈顶3大,出栈,栈为[7,4],返回数组为[7,-1,-1,5,-1],又比栈顶[4]大，4出栈，栈为[7]，返回数组为[7,-1,5,5,-1]，最后5也入栈，栈为[7,5]。
由于链表已经遍历完毕，此时栈中的元素都是我们要设置为0的元素，对栈进行清空在清空的过程中进行操作即可。
