五月集训-12【链表】

• 前言
• 一、练习题目
• 二、思路及题解
• • 1. LC1290-二进制链表转整数
  • 2. LC237-删除链表中的节点
  • 3. LC206-反转链表
  • ^*^4. LC1019-链表中的下一个更大节点
• 总结

        欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 链表 专题，更多其他专题内容详见《LeetCode每月集训系列》

方法一：

（1）使用位运算计算二进制数，先读到的是二进制的低位。

代码如下：

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int sum = 0;
        while (head) {
            sum = (sum << 1 | head -> val);
            head = head -> next;
        }
        return sum;
    }
};

方法一：

（1）由于无法访问头结点，因此需要转换一些思维，将下一个结点的值赋给要删除节点的值，然后删除下一个结点即可。

代码如下：

class Solution {
public:
    void deleteNode(ListNode* node) {
        node -> val = node -> next -> val;
        node -> next = node -> next -> next;
    }
};

方法一：

（1）遍历链表，不断将当前节点的 next 指针改为指向前一个节点。

代码如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp;
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 暂存cur的下一个节点
            cur->next = pre;  // 翻转操作
            // 更新pre和cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

方法一：单调栈

（1）首先将链表中的所有元素都转移到一个 nums数组中;
（2）创建一个单调递增栈，栈中存储的是数组中元素的下标，从栈顶到栈底每个元素对应数组中的值是递增的；
（3）遍历 nums 数组，若栈为空，则直接将当前遍历元素的下标入栈；若栈不为空并且栈顶位置的元素小于当前遍历的元素，则说明栈顶位置的元素找到了它的下一更大节点值，直接在将要返回的数组中赋值即可。

代码如下：

class Solution {
public:
    vector nextLargerNodes(ListNode* head) {
        stack stk;
        vector temp;
        while(head != NULL){
            temp.push_back(head -> val);
            head = head -> next;  
        }
        
        vector res(temp.size(),0);
        for(int i = 0; i < temp.size(); ++i){
            while(!stk.empty() && temp[stk.top()] < temp[i]) {
                res[stk.top()] = temp[i];
                stk.pop();
            }
            stk.push(i);
        }
        return res;
    }
};

        题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️