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

算法专题八: 链表

article 2024/10/23 13:06:36

目录

  • 链表
  • 1. 链表的常用技巧和操作总结
  • 2. 两数相加
  • 3. 两两交换链表中的节点
  • 4. 重排链表
  • 5. 合并K个升序链表
  • 6. K个一组翻转链表

链表

1. 链表的常用技巧和操作总结

  • 常用技巧
  1. 画图!!! 更加直观形象, 便于我们理解
  2. 引入虚拟头节点, 方便我们对链表的操作, 减少我们对边界情况的考虑. 如果没有虚拟头节点我们可能还需要考虑头插时候的情况进行特殊处理

在这里插入图片描述
3. 不要吝啬空间, 大胆定义变量
4. 快慢双指针, (判环, 找链表中环的入口, 找链表中倒数第n个节点)

  • 链表中的常用操作
  1. 创建一个新的节点 使用new
  2. 尾插的方法
  3. 头插的方法 (逆序链表)

2. 两数相加

在这里插入图片描述

算法原理:

模拟两数相加的过程即可, 使用头插, 取l1的数, l2的数, 累加到t中.

在这里插入图片描述

编写代码:

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* newhead = new ListNode;
        ListNode* prev = newhead;
        ListNode* cur1 = l1, *cur2 = l2;
        int t = 0;
        while(cur1 || cur2 || t)
        {
            if(cur1)
            {
                t += cur1->val;
                cur1 = cur1->next;
            }
            if(cur2)
            {
                t += cur2->val;
                cur2 = cur2->next;
            }
            ListNode* add = new ListNode(t % 10);
            prev = prev->next = add;
            t /= 10;
        }
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};

3. 两两交换链表中的节点

在这里插入图片描述

算法思路: 方法一是使用递归的方法, 方法二就是使用模拟
在这里插入图片描述
不要吝啬指针的定义只要我们定义好了上述指针就会发现仅需遍历一遍链表即可讲链表进行交换, 先进行交换, 这里需要修改到三个指针, 如果为偶数的情况下cur和next都不为空, 如果为奇数的情况下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:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = new ListNode;
        ListNode* prev = newhead, *cur = head, *next = head->next, *nnext = next->next;
        while(cur && next)
        {
        //交换节点
            prev->next = next;
            next->next = cur;
            cur->next = nnext;
            //修改指针
            prev = cur;
            cur = nnext;
            if(cur) next = cur->next;
            if(next) nnext = next->next;
        }
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

4. 重排链表

在这里插入图片描述

算法思路:

在这里插入图片描述

这里把slow后面的部分逆序有两种策略, 第一种包括slow位置, 第二种slow->next的位置进行逆序, 如果按照第二种可以直接slow->next = nullptr讲链表置为空, 如果第一种想要将链表置空需要遍历的时候记录一下位置, 这里我们采用第二种方式只把slow->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:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* cur = slow->next;
        slow->next = nullptr; 
        ListNode* prev = nullptr;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        ListNode* l1 = head;
        ListNode* l2 = prev;
        ListNode* newhead = new ListNode; 
        prev = newhead;
        while(l1)
        {
            prev = prev->next = l1;
            l1 = l1->next;
            if(l2)
            {
                prev = prev->next = l2;
                l2 = l2->next;
            }
        }
        delete 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:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return; //处理边界情况
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        //头插法进行逆置slow->next后面的部分
        ListNode* head2 = new ListNode;
        ListNode* cur = slow->next;
        slow->next = nullptr;//断开链表
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = head2->next;
            head2->next = cur;
            cur = next;
        }
        //合并两个链表尾插
        ListNode* cur1 = head, *cur2 = head2->next;
        ListNode* ret = new ListNode;
        ListNode* prev = ret;
        while(cur1)
        {
            prev->next = cur1;
            prev = prev->next; 
            cur1 = cur1->next;

            if(cur2)
            {
                prev->next = cur2;
                prev = prev->next;
                cur2 = cur2->next;
            }
        }
        delete ret;
        delete head2;
        return;   
    }
};

5. 合并K个升序链表

在这里插入图片描述

算法思路:

在这里插入图片描述
暴力解法时间复杂度太高了, 而且比较麻烦

  1. 模拟, 使用堆这个数据结构, 重载比较函数, 先将所有的头节点插入到堆中, 然后取堆顶元素进行合并, 合并之后如果下一个元素存在把下一个元素插入到堆中, 如果堆为空则合并完毕, 注意这里的const修饰的是指针本身, 而不是修饰这个变量, 因为这个变量不是const类型变量, const位置放置错误会导致报错, 注意类型匹配.

在这里插入图片描述

/**
 * 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:
    class com
    {
    public:
        bool operator()(ListNode* const &l1, ListNode* const &l2)
        {
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>,com> heap;
        for(auto x : lists)
            if(x) heap.push(x);
        ListNode* newhead =new ListNode;
        ListNode* prev = newhead;
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            prev = prev->next = t;
            heap.pop();
            if(t->next) heap.push(t->next);
        }
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};
  1. 递归

在这里插入图片描述

/**
 * 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 mergeSort(lists,0,lists.size()-1);
    }
    ListNode* mergeSort(vector<ListNode*>& lists,int left,int right)
    {
        //处理边界
        if(left > right) return nullptr;
        if(left == right) return lists[left];
        //划分区间
        int mid = (right + left) >> 1;
        ListNode* l1 = mergeSort(lists, left, mid);
        ListNode* l2 = mergeSort(lists,mid+1, right);

        //排列
        return mergelist(l1,l2);
    }
    ListNode* mergelist(ListNode* l1, ListNode* l2)
    {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        ListNode* newhead = new ListNode;
        ListNode* prev = newhead;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                prev = prev->next = l1;
                l1 = l1->next;
            }
            else
            {
                prev = prev->next = l2;
                l2 = l2->next;
            }
        }
        if(l1) prev->next = l1;
        if(l2) prev->next = l2;
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};

6. 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* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head; int n = 0;
        while(cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;
        ListNode* newhead = new ListNode;
        ListNode* prev = newhead;
        cur = head;
        for(int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for(int j = 0; j < k; j++)
            {
                ListNode* next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
                cur = next;
            }
            prev = tmp;
        }
        prev->next = cur;
        cur = newhead->next;
        delete newhead;
        return cur;
    }
};

完


http://www.kler.cn/news/361598.html

相关文章：

  • LINUX设备OTA时无法从HTTP服务器（TOMCAT）下载文件
  • Python实现文本数据可视化：构建动态词云
  • 数据结构与算法：贪心算法与应用场景
  • 保姆级VsCode配置C++编译环境
  • Linux LVS详解
  • Java中的HashMap和Hashtable有什么区别？
  • 9. JSON RPC 服务
  • Java最全面试题-＞Java基础面试题-＞JavaWeb面试题-＞Git/SVN面试题
  • Spring Boot助力：构建响应式论坛网站
  • python 结构作业
  • Maven项目管理工具-初始+环境配置
  • Anthropic 发布Claude 3.5 Haiku 以及一项炸裂的新功能 AI可以模仿人类访问电脑
  • 【Linux系统编程】第三十六弹---深入探索进程间通信：封装共享内存类并实现进程间数据共享
  • 点跟踪论文—RAFT: Recurrent All-Pairs Field Transforms for Optical Flow-递归的全对场光流变换
  • Python基础——类与对象
  • C++算法练习-day15——1.两数之和
  • 打造开放式语音智能体
  • 拴柱说Mac之Mac的高效使用技巧第三期
  • 源码编译方式安装htppd软件
  • mysql学习教程，从入门到精通，SQL导入数据（44）
  • Java重修笔记 UDP 网络通信
  • python从0快速上手（十六）小游戏开发
  • 某科技——北京——国护蓝中研判岗
  • 至多六步，linux挂载磁盘
  • DORA 机器人中间件学习教程（6）——激光点云预处理
  • 电脑输入账号密码后,屏幕黑屏只有鼠标解决办法