当前位置： 首页 > article >正文

算法：常见的链表算法

article 2024/11/13 14:12:12

文章目录

  • 链表算法
  • 两数相加
    • 两两交换链表中的节点
    • 重排链表
    • 合并K个升序链表
    • K个一组翻转链表
  • 总结

本篇总结常见的链表算法题和看他人题解所得到的一些收获

链表算法

关于链表的算法：

  1. 画图：画图可以解决绝大部分的数据结构的问题，任何的算法题借助图都可以有一个比较清晰的思路
  2. 引入哨兵位头节点：头节点可以避免处理很多边界情况，在解决一些问题前很方便
  3. 多定义几个变量：可以很方便的解决问题
  4. 快慢指针：在处理带环的问题，环的入口，倒数节点的时候很好用

两数相加

在这里插入图片描述

在这里积累这个题的目的是学习代码的写法，学习他人的代码

这是自己的代码：

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* newhead = new ListNode();
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* cur = newhead;
        int carry = 0, sum = 0, ret = 0;

        while(cur1 && cur2)
        {
            // 计算出这个节点要存的值是多少
            sum = cur1->val + cur2->val + carry;
            carry = sum / 10;
            ret = sum % 10;
            
            // 插入节点
            ListNode* newnode = new ListNode(ret);
            cur->next = newnode;
            cur = newnode;

            // 迭代
            cur1 = cur1->next;
            cur2 = cur2->next;
        }

        while(cur1)
        {
            // 计算出这个节点要存的值是多少
            sum = cur1->val + carry;
            carry = sum / 10;
            ret = sum % 10;

            // 插入节点
            ListNode* newnode = new ListNode(ret);
            cur->next = newnode;
            cur = newnode;

            // 迭代
            cur1 = cur1->next;
        }

        while(cur2)
        {
            // 计算出这个节点要存的值是多少
            sum = cur2->val + carry;
            carry = sum / 10;
            ret = sum % 10;

            // 插入节点
            ListNode* newnode = new ListNode(ret);
            cur->next = newnode;
            cur = newnode;

            // 迭代
            cur2 = cur2->next;
        }

        if(carry)
        {
            // 插入节点
            ListNode* newnode = new ListNode(carry);
            cur->next = newnode;
            cur = newnode;
        }

        return newhead->next;
    }
};

运行可以通过，但是代码量比较冗余，其实可以发现while循环和后面的if语句有相当多的相似语句，因此看下面的代码：

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode* newhead = new ListNode();
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* cur = newhead;
        int sum = 0;

        while(cur1 || cur2 || sum)
        {
            // 先加第一个链表
            if(cur1)
            {
               sum += cur1->val;
               cur1 = cur1->next;
            }

            // 再加第二个链表
            if(cur2)
            {
                sum += cur2->val;
                cur2 = cur2->next;
            }

            // 处理节点数据
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            sum /= 10;
        }

        // 处理掉不必要的内存空间
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

两两交换链表中的节点

在这里插入图片描述
其实这个题已经见过很多次了，有很多种解决方法，直接模拟，递归…

但是这里积累它的意义在于，引入虚拟头节点对于解题是很有帮助的

/**
 * 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* swapPairs(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr)
            return head;
        
        ListNode* newhead = new ListNode();
        newhead->next = head;
        ListNode* prev = newhead;
        ListNode* cur = newhead->next;
        ListNode* next = cur->next;
        ListNode* nnext = next->next;
        while(cur && next)
        {
            // 交换节点
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            // 迭代
            prev = cur;
            cur = prev->next;
            if(cur) next = cur->next;
            if(next) nnext = next->next;
        }

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

不带虚拟头节点：

/**
 * 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* swapPairs(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr)
            return head;
        // 先找到新的头节点
        ListNode* newhead = head->next;
        // 找到当前待交换的两个节点
        ListNode* left = head;
        ListNode* right = head->next;
        while(left && right)
        {
            // 交换两个节点
            left->next = right->next;
            right->next = left;
            // 进行迭代
            ListNode* prev = left;
            left = left->next;
            if(left)
            {
                right = left->next;
                if(right)
                    prev->next = right;
            }
        }

        return newhead;
    }
};

递归解题

/**
 * 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* swapPairs(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* left = head;
        ListNode* right = left->next;
        ListNode* tmp = right->next;
        right->next = left;
        left->next = swapPairs(tmp);
        return right;
    }
};

重排链表

在这里插入图片描述
积累本题的意义在于，本题综合了逆序链表，快慢指针，链表插入的问题，是一个综合性的题

/**
 * 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:
    void reorderList(ListNode* head) 
    {
        // 利用快慢双指针找到中间节点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        // 得到两个新链表
        ListNode* newheadleft = head;
        ListNode* newheadright = Reverse(slow->next);
        slow->next = nullptr;

        // 把这两个链表再组装起来
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        ListNode* cur1 = newheadleft;
        ListNode* cur2 = newheadright;
        while(cur1 || cur2)
        {
            if(cur1)
            {
                tail->next = cur1;
                tail = tail->next;
                cur1 = cur1->next;
            }
            if(cur2)
            {
                tail->next = cur2;
                tail = tail->next;
                cur2 = cur2->next;
            }
        }

        ListNode* res = newhead->next;
        delete newhead;
        head = res;
    }

    ListNode* Reverse(ListNode* head)
    {
        ListNode* newhead = new ListNode();
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

合并K个升序链表

在这里插入图片描述

关于这个题，乍一看其实是很难想到用什么方法做的，而实际上如果要是使用优先级队列或者是递归的思想来解题是可以解决的，算法的思路难，但是实际的变现并不难

这里提供三种解题方法：暴力求解、利用优先级队列来解题、利用归并的思想来解题

暴力求解

/**
 * 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* mergeKLists(vector<ListNode*>& lists) 
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        for(int i = 0; i < lists.size(); i++)
        {
            merge(newhead->next, lists[i]);
        }
        return newhead->next;
    }

    void merge(ListNode*& head, ListNode* cur)
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        while(head && cur)
        {
            if(head->val < cur->val)
            {
                tail->next = head;
                tail = tail->next;
                head = head->next;
            }
            else
            {
                tail->next = cur;
                tail = tail->next;
                cur = cur->next;
            }
        }
        if(head) tail->next = head;
        if(cur) tail->next = cur;

        head = newhead->next;
    }
};

利用优先级队列的思想解题

/**
 * 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:
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
    // 利用优先级队列进行优化
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        
        // 把每一个链表都塞进去
        for(int i = 0; i <lists.size(); i++)
        {
            if(lists[i])
                pq.push(lists[i]);
        }
        
        // 创建虚拟头节点，开始链入到链表中
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;

        // 找到最小的节点，拿出来，再把它的下一个节点再塞进去，直到队列为空
        while(!pq.empty())
        {
            ListNode* top = pq.top();
            pq.pop();
            if(top != nullptr)
            {
                ListNode* next = top->next;
                top->next = nullptr;
                // 塞到目标链表中
                tail->next = top;
                tail = tail->next;
                // 再把剩下的部分再塞进去
                if(next)
                    pq.push(next);
            }
        }

        // 返回信息
        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

利用归并的思想解题

/**
 * 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* mergeKLists(vector<ListNode*>& lists) 
    {
        return merge(lists, 0, lists.size() - 1);
    }

    // 归并排序
    ListNode* merge(vector<ListNode*>& lists, int left, int right)
    {
        // 处理特殊情况
        if(left > right) return nullptr;
        if(left == right) return lists[left];

        // 拆分数组
        int midi = left + (right - left) / 2;
        // [left, midi][midi + 1, right]
        ListNode* l1 = merge(lists, left, midi);
        ListNode* l2 = merge(lists, midi + 1, right);

        // 排序
        return mergetwonode(l1, l2);
    }

    // 合并链表
    ListNode* mergetwonode(ListNode* l1, ListNode* l2)
    {
        ListNode* newhead = new ListNode();
        ListNode* cur1 = l1, *cur2 = l2, *tail = newhead;
        
        while(cur1 && cur2)
        {
            if(cur1->val <= cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
                tail = tail->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
                tail = tail->next;
            }
        }

        if(cur1) tail->next = cur1;
        if(cur2) tail->next = cur2;

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

K个一组翻转链表

在这里插入图片描述

/**
 * 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 
{
    // 思路：把链表k个一组拿出来，再翻转，再链入一个新的链表中
public:
    ListNode* reverseKGroup(ListNode* head, int k) 
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        ListNode* left = head, *right = left;

        while(left && right)
        {
            // 把链表k个一组分出来
            for(int i = 1; i < k; i++)
            {
                // 如果此时已经到最后了，那么这最后一组就不需要进行翻转
                if(right == nullptr)
                {
                    tail->next = left;
                    return newhead->next;
                }
                right = right->next;
            }
            // 断链
            if(right)
            {
                ListNode* newleft = right->next;
                right->next = nullptr;
                // 现在从[left, right]就是一段完整的不带头节点的链表了
                // 把这段链表进行翻转，并链入到新的链表中
                tail->next = reverse(left);
                tail = left;
                // 迭代，找下一组k个节点
                left = newleft, right = left;
            }
        }
        tail->next = left;
        return newhead->next;
    }

    // 进行链表的反转
    ListNode* reverse(ListNode* cur)
    {
        ListNode* newhead = new ListNode();
        
        // 把链表中的节点头插到新链表中
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newhead->next;
            newhead->next = cur;
            cur = next;
        }

        ListNode* res = newhead->next;
        delete newhead;
        return res;
    }
};

这个题的难点在于细节问题的处理，其实思路并不难

总结

其实对于链表这一块的算法主要是体现在需要处理一些边界情况和循环调用带来的问题，通过借助虚拟头节点和多创建几个指针可以缓解这种情况，主要是细节要处理好，对于思维的需求没有那么高


http://www.kler.cn/a/163115.html

相关文章：

  • 问：MySQL主从同步的机制梳理？
  • 【电力系统】永磁同步电机调速系统带有扰动观测器
  • 力扣 LeetCode 977. 有序数组的平方（Day1：数组）
  • 关于Oracle数据库密码复杂度检查的一些概念
  • 大数据学习12之HBase
  • 揭开 gRPC、RPC 、TCP和UDP 的通信奥秘
  • 插入排序——直接插入排序和希尔排序(C语言实现）
  • 如何进行更好的面试回复之缓存函数在项目中的性能优化？
  • Advanced Renamer
  • 利用R语言heatmap.2函数进行聚类并画热图
  • Shell脚本如何使用 for 循环、while 循环、break 跳出循环和 continue 结束本次循环
  • Vue学习笔记-Vue3中的计算属性与监视属性
  • 【数据结构】拆分详解 - 二叉树的链式存储结构
  • 消费升级：无人零售的崛起与优势
  • 【MATLAB源码-第97期】基于matlab的能量谷优化算法(EVO)机器人栅格路径规划，输出做短路径图和适应度曲线。
  • git操作:使用vscode集成
  • Spring Cloud Gateway中对admin端点进行认证
  • 自动补全的 select antd react
  • php+mysql期末作业小项目
  • kafka学习笔记--安装部署、简单操作
  • luceda ipkiss教程 43：画渐变圆弧型波导
  • ModuleNotFoundError: No module named ‘dlib‘
  • C_15练习题
  • Qt与Sqlite3
  • 车联网软件定义汽车安全攻击示例
  • 第15章：随堂复习与企业真题（File类与IO流）