程序员经验分享-hwhale

day1 牛客TOP100：BM 1-10 链表

2023-11-07

链表

BM1 反转链表

题目
在这里插入图片描述

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* temp;
        while(cur)
        {
            temp = cur->next;//保存cur下一个节点
            cur->next = pre;//反转
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

BM2 链表内指定区间反转

在这里插入图片描述
自己写的时候，思路正确，但是处理不好反转后的拼接

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m == n) return head;
        ListNode* dummyhead = new ListNode(-1);
        dummyhead->next = head;

        //反转链表的前部分
        ListNode* start = dummyhead;
        for(int i=1; i<m; i++)
            start = start->next;//结点1
        cout << "start: "<< start->val <<endl;
        
        //反转链表的尾巴 第n个结点
        ListNode* right = start->next;
        for(int i=m; i<n; i++)
            right = right->next;//结点4
        cout << "right: "<< right->val <<endl;

        //反转链表的头尾
        ListNode* left = start->next;//2
        ListNode* end = right->next;//5
        
        //切断 left 1 2 3 4
        start->next = nullptr;
        right->next = nullptr;
        reverlist(left);

        //接回原来的链表
        start->next = right;//1->4
        left->next = end;//2->5
        return dummyhead->next;
    }
    void reverlist(ListNode* node)
    {
        ListNode* pre = nullptr;
        ListNode* cur = node;
        ListNode* temp;
        while(cur)
        {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
    }
};

写法2

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m == n) return head;
        ListNode* dummyhead = new ListNode(-1);
        dummyhead->next = head;

        //写法1
        /*//反转链表的前部分
        ListNode* start = dummyhead;
        for(int i=1; i<m; i++)
            start = start->next;//结点1
        cout << "start: "<< start->val <<endl;
        
        //反转链表的尾巴 第n个结点
        ListNode* right = start->next;
        for(int i=m; i<n; i++)
            right = right->next;//结点4
        cout << "right: "<< right->val <<endl;

        //反转链表的头尾
        ListNode* left = start->next;//2
        ListNode* end = right->next;//5
        
        //切断 left 1 2 3 4
        start->next = nullptr;
        right->next = nullptr;
        reverlist(left);

        //接回原来的链表
        start->next = right;//1->4
        left->next = end;//2->5
        return dummyhead->next;*/

        //写法2
        ListNode* pre = dummyhead;
        ListNode* cur = head;
        
        //找到结点m
        for(int i=1; i<m; i++)
        {
            pre = cur;//m-1
            cur = cur->next;//m
        }
        //从m到n反转 依次断掉指向后续的指针，反转指针方向
        ListNode* temp;
        for(int i=m; i<n; i++)
        {
            temp = cur->next;//要反转的结点
            cur->next = temp->next;//指向n
            temp->next = pre->next;//反转
            pre->next = temp;//指向m
        }
        return dummyhead->next;

    }
    void reverlist(ListNode* node)
    {
        ListNode* pre = nullptr;
        ListNode* cur = node;
        ListNode* temp;
        while(cur)
        {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
    }
};

BM3 链表中的节点每k个一组翻转

在这里插入图片描述
自己写的乱七八糟，看了解答之后觉得好聪明啊，关键是要找到反转前的局部链表的尾巴，这个也是要返回的链表头，然后建立每一组的连接！！

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //每一组局部链表的表头 反转前局部链表的尾巴 
        ListNode* tail = head;
        //找到尾巴
        for(int i=0; i<k; i++)
        {
            //如果链表不够长 返回结果
            if(tail == nullptr) return head;
            tail = tail->next;
        }

        //反转局部链表
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* temp;
        //在到达当前段尾节点前
        while(cur != tail)
        {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        //反转后链表尾部连接下一组表头
        head->next = reverseKGroup(tail, k);
        return pre;
    }
};

模拟的写法，将一条链表分为链表长度/k块链表，如果处不尽则说明后面会有剩下的那一块是不满长度为k的。
最初需要定义虚拟表头dummyhead（最终结果）和局部链表的反转前的表头start。然后遍历每一组局部链表，并反转。反转后需要将start与反转后的局部链表头pre连接（反转前局部链表的尾部），再更新下一组的局部链表的表头，也就是将start更新到最前。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k<=1) return head;
        if(head == nullptr) return nullptr;

        int len = getLength(head);
        int part = len / k;//分组

        ListNode* dummyhead = new ListNode(-1);
        ListNode* start = dummyhead;//每一组局部链表的表头
        for(int i=0; i<part; i++)
        {
            //局部链表反转后的尾巴
            ListNode* pre = nullptr;
            for(int j=0; j<k; j++)
            {
                ListNode* temp = head->next;
                head->next = pre;
                pre = head;
                head = temp;
            }
            start->next = pre;//链表头连接 反转后的局部链表 的表头
            while(start->next) start = start->next;//更新下一组的表头
        }
        start->next = head;
        return dummyhead->next;

    }
private:
    //获取链表长度
    int getLength(ListNode* node)
    {    
        int len = 0;
        if(node == nullptr) return len;
        while(node)
        {
            len++;
            node = node->next;
        }
        return len;
    }
};

BM4 合并两个排序的链表

在这里插入图片描述

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1 && !pHead2) return nullptr;
        if(!pHead1) return pHead2;
        if(!pHead2) return pHead1;

        ListNode* dummyhead = new ListNode(-1);
        ListNode* cur = dummyhead;
        while(pHead1 && pHead2)
        {
            if(pHead1->val <= pHead2->val)
            {
                cur->next = pHead1;
                pHead1 = pHead1->next;//1->2
                //cout << "   cur:" << cur->next->val << "  pHead1:" << pHead1->val << endl;
            }
            else if(pHead1->val > pHead2->val)
            {
                cur->next = pHead2;
                pHead2 = pHead2->next;
                //cout << "   cur:" << cur->next->val << "  pHead2:" << pHead2->val << endl;
            }
            cur = cur->next;//连接新链表
        }
        //如果还有剩下的结点 单独处理最后一个结点
        cur->next = (pHead2 == nullptr) ? pHead1 : pHead2;
        return dummyhead->next;
    }
};

方法2，取较小的结点

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1 && !pHead2) return nullptr;
        if(!pHead1) return pHead2;
        if(!pHead2) return pHead1;
        ListNode* dummyhead = new ListNode(-1);
        ListNode* cur = dummyhead;
        while(pHead1 && pHead2)
        {
            if(pHead1->val > pHead2->val) swap(pHead1, pHead2);
            cur->next = pHead1;//建立新连接
            pHead1 = pHead1->next;//更新
            cur = cur->next;//更新
        }
        cur->next = (pHead2 == nullptr) ? pHead1 : pHead2;
        return dummyhead->next;
    }
};

BM5 合并k个已排序的链表

在这里插入图片描述

这个写法会把负数的结点吞掉，例如输入：[{-5},{-9,-8,-7,-5,1,1,1,3},{-10,-7,-6,-6,-6,0,1,3,3},{-10,-8,-7,-2,3,3},{-1,4},{-5,-4,-1}]，输出是{-5,0,1,1,1,1,3,3,3,3,3,4}

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        ListNode* dummyhead = new ListNode(-1);
        dummyhead->next = lists[0];
        ListNode* cur = dummyhead;
        for(int i=1; i<lists.size();)
        {
            cur->next = mergeList(lists[i], lists[i+1]);
            cur = cur->next;
            i += 2;
        }
        return dummyhead->next;
    }
    ListNode* mergeList(ListNode* head1, ListNode* head2)
    {
        if(head1 == nullptr) return head2;
        if(head2 == nullptr) return head1;
        ListNode* dummyhead =  new ListNode(0);
        ListNode* cur = dummyhead;
        while(head1 && head2)
        {
            if(head1->val >= head2->val) swap(head1, head2);
            cur->next = head1;
            head1 = head1->next;
            cur = cur->next;
        }
        cur->next = (head1 == nullptr) ? head2 : head1;
        return dummyhead->next;
    }

};

加入并归排序后的，可以输出负数结点了

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divideMerge(lists, 0, lists.size()-1);
    }
    //划分合并区间函数
    ListNode* divideMerge(vector<ListNode *> &lists, int left, int right){
        if(left > right)
            return NULL;
        //中间一个的情况
        else if(left == right)
            return lists[left];
        //从中间分成两段，再将合并好的两段合并
        int mid = (left + right) / 2;
        return mergeList(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right));
    }
    ListNode* mergeList(ListNode* head1, ListNode* head2)
    {
        if(!head1 && !head2) return nullptr;
        if(head1 == nullptr) return head2;
        if(head2 == nullptr) return head1;
        ListNode* dummyhead =  new ListNode(0);
        ListNode* cur = dummyhead;
        while(head1 && head2)
        {
            if(head1->val >= head2->val) swap(head1, head2);
            cur->next = head1;
            head1 = head1->next;
            cur = cur->next;
        }
        cur->next = (head1 == nullptr) ? head2 : head1;
        return dummyhead->next;
    }

};

BM6 判断链表中是否有环

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

思路就是，快慢指针同时出发，慢指针走一步，快指针走两步。快指针肯定先进入环，慢指针后入环，如果两个指针相遇说明有环，如果没有相遇，遍历结束说明没有换。

第一次写的时候，有一组很长的链表没有通过，while循环内没有对fast的下一个结点进行判断，可能会一直在循环里边不终止。加了一个判断，如果fast有下一个结点才更新，否则也是说明链表走到头了。又或者是while的判断条件加上fast->next != null

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && slow)
        {
            slow = slow->next;
            //下面这个if-else是改正后的写法
            if(fast->next) fast = fast->next->next;
            else return false;
            if(fast == slow) return true;
        }
        return false;//如果fast先遇到null说明没有环
    }
};

BM7 链表中环的入口结点

在这里插入图片描述
上一题是判断有没有环，这个是有环然后要找到环入口。

思路，也是快慢指针。

  • 首先，快慢指针同时出发，慢指针走一步，快指针走两步。快指针肯定先进入环，慢指针后入环，如果两个指针相遇说明有环，如果没有相遇，遍历结束说明没有环。
  • 然后，第一次相遇时，在这个地方，重新定义两个指针，慢指针从头开始走，快指针在换里边走同时移动一步，如果相遇就找到了环入口，否则返回null。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead == nullptr) return nullptr;
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(fast!=nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                slow = pHead;
                ListNode* entrynode = fast;
                while(entrynode)
                {
                    //先判断 有可能就是一个闭环链表
                    if(entrynode == slow) return entrynode;
                    slow = slow->next;
                    entrynode = entrynode->next;
                }
            }
        }
        return nullptr;
    }
};

BM8 链表中倒数最后k个结点

在这里插入图片描述
思路-快慢指针：

  • 首先，快指针先走K步，在这里要注意两个特殊情况，一个是链表不够长，一个是正好需要返回倒数最后一个结点（第一个结点）。
  • 然后，慢指针从头开始，和快指针同时前进，快指针走到链表尾，慢指针走到第k个结点了。
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        //空链表
        if (pHead == nullptr) return pHead;
        ListNode* fast = pHead;
        while(k--)
        {
            if(fast->next == nullptr && k>0) return nullptr;//链表不够长
            if(fast->next == nullptr) return pHead;//倒数最后一个
            fast = fast->next;
            //cout << "  fast: " << fast->val;
        }
        while(fast)
        {
            pHead = pHead->next;
            fast = fast->next;
        }
        return pHead;
    }
};

BM9 删除链表的倒数第n个节点

在这里插入图片描述
思路在上一题的基础上，在保存一个倒数第K-1个节点，然后逻辑删除就可以了。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == nullptr) return head;
        ListNode* fast = head;
        while(n--)
        {
            if(fast->next==nullptr && n>0) return nullptr;
            if(fast->next==nullptr)
            {
                return head->next;//逻辑删除
            }
            cout << "  fast: " << fast->val;
            fast = fast->next;
        }
        ListNode* slow = head;
        ListNode* temp;
        while(fast)
        {
            temp = slow;//倒数第k-1个结点
            slow = slow->next;//倒数第k个结点
            fast = fast->next;
        }
        temp->next = slow->next;
        return head;
    }
};

BM10 两个链表的第一个公共结点

在这里插入图片描述
思路：统计长度，计算长度差len，长的链表先走len步，然后再和短链表一起走，如果两结点相同说明有公共结点。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1 || !pHead2) return nullptr;
		int len1 = getLenofList(pHead1);
		int len2 = getLenofList(pHead2);
		if(len1 < len2)
		{
			swap(pHead1, pHead2);
			swap(len1, len2);	
		}
		int len = len1 - len2;
		while(len--)
		{
			pHead1 = pHead1->next;
		}
		//cout << pHead1->val<<endl;
		while(pHead1)
		{
			if(pHead1 == pHead2) return pHead1;
			pHead1 = pHead1->next;
			pHead2 = pHead2->next;
		}
		return nullptr;
    }
	int getLenofList(ListNode* head)
	{
		int res = 0;
		if(head == nullptr) return res;
		while(head)
		{
			res++;
			head = head->next;
		}
		return res;
	}
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

C刷题LeetCode牛客

c

day1 牛客TOP100：BM 1-10 链表 的相关文章

随机推荐

  • 常见的线性滤波和非线性滤波

    在OpenCV中给出了给出了3种常见的线性滤波和2种非线性滤波 其中线性滤波分别为方框滤波 均值滤波和高斯滤波 非线性滤波分别为中值滤波和双边滤波 关于它们的具体介绍后续会补充

  • 光线追踪（RayTracing）算法

    1 Forward Tracing 假设有一个每次只发射一个光子的光源 光子从光源发出并沿着直线路径行进 直至撞击到物体表面 忽略光子的吸收 该光子会以随机的方向反射 如果光子撞击到我们的眼睛表面 则我们会看到光子被反射的点 现在从计算机图

  • 输入整数数组排序

    题目描述 输入整型数组和排序标识 对其元素按照升序或降序进行排序 示例1 输入 8 1 2 4 9 3 55 64 25 0 输出 1 2 3 4 9 25 55 64 分析 Java自带数组排序方法 Arrays sort 将数组排序后

  • 串口一键下载电路（CH340）的理解

    如图 为原子的串口下载电路 在CH340的数据手册上有引脚的介绍以及作用 这两个引脚 DTR 和RTS 都是 输出类型 MCUISP 一键下载工具 会控制CH340这两个引脚的高低电平状态 通过控制DTR 和RST 这两个引脚的高低电平状态

  • SOCKS 5协议详解 　

    SOCKS 5协议详解 笔者在实际学习中 由于在有些软件用到了socks5 如oicq icq等 对其原理不 甚了解 相信很多朋友对其也不是很了解 于是仔细研读了一下rfc1928 觉得有必要 译出来供大家参考 1 介绍 防火墙的使用 有效

  • python生成复合饼图

    可以通过matplotlib实现 from matplotlib patches import ConnectionPatch 制画布 fig plt figure figsize 9 5 0625 ax1 fig add subplot

  • android问题及解决方案,Android开发中常见问题及解决方案

    Android开发中常见问题及解决方案 1 什么是Activity activity是Android组件中最基本也是最为常见用的四大组件之一 Android四大组件有Activity活动 Service服务 Content Provider

  • IDEA如何快速引入局部变量

    alt 回车就行

  • 795. 前缀和

    文章目录 Question Ideas Code Question 输入一个长度为 n 的整数序列 接下来再输入 m 个询问 每个询问输入一对 l r 对于每个询问 输出原序列中从第 l 个数到第 r 个数的和 输入格式 第一行包含两个整数

  • [1198]ApkScan-PKID 查壳工具

    文章目录 一 关于壳的介绍 二 关于壳的技术资料 三 APKSCAN PKID的下载 四 APKSCAN PKID的使用 总结 脱壳工具 一 关于壳的介绍 1 壳的功能 壳最本质的功能就是实现加载器 壳是指在一个程序的外面再包裹上另外一段代

  • 计算机2.0培训心得,信息技术2.0心得体会

    以下为 信息技术2 0心得体会 的无排版文字预览 完整格式请下载 下载前请仔细阅读文字预览以及下方图片预览 图片预览是什么样的 下载的文档就是什么样的 信息技术培训2 0学习心得体会 今年11月有机会参加信息技术培训 对我各方面的能力有了很

  • 基于SpringBoot和微信小程序的点餐系统(毕业设计论文)

    声明 本篇博客是我本科毕设论文 虽然研究课题比较普遍且较为简单 但已达到毕设要求 考虑到以后的查重问题 顾本篇博客将采用论文局部图片的形式展示 有想研究并想作为毕设的童鞋也可以拿来参考 需要源码 调试 论文 答辩材料见文章末尾哦 论文目录

  • 如何在jupyter notebook下导入模块

    在jupyter notebook下编写的脚本文件的后缀是 ipynb 比如我写了一个名为Test ipynb的模块 如果直接按照python的导入方式直接导入的时候会出现 正确的做法是先将 ipynb导成 py的格式 然后再调用就OK了

  • cmd复制文件

    cmd复制文件 复制文件夹 自动覆盖 xcopy E I Y D GitHub Qriket lucky SPA dist D GitHub lucky www 复制单个文件 自动覆盖 copy Y D GitHub lucky platf

  • 路由器】路由器3G类异常，即3G业务不定时中断，造成过一段时间后业务可以自动恢复，或者必须通过重启路由器等操作业务才能够恢复

    1 故障现象 3G路由器下的业务出现不定时中断的现象 过一段时间后业务可以自动恢复 或者必须通过重启路由器等操作业务才能够恢复 2 故障可能原因 1 3G客户端或LNS设备运行异常 2 3G客户端或LNS相关参数配置不合理 3 3G客户端和

  • BP神经网络算法推导（包含输出层和隐层）

    你是否也有疑问 在神经网络的训练过程中 随着多样本的训练 我们的参数是如何进行调节的呢 答案自然就是BP算法 Error Back Propagation 反向传播时 将输出误差 期望输出与实际输出之差 按原通路反传计算 通过隐层反向 直至

  • Anaconda+TensorFlow安装和Pycharm配置深度学习环境详细教程！

    配置Anaconda Pycharm学习环境 大体分为三步骤 一 Anaconda的下载与安装 二 PyCharm的下载与安装 三 Anaconda Pycharm配置环境 下载好的资源链接 链接 https pan baidu com s

  • 分布式 datax 架构设计

    1 背景 DataX 是一个异构数据源离线同步工具 致力于实现包括关系型数据库 MySQL Oracle 等 HDFS Hive ODPS HBase FTP 等各种异构数据源之间稳定高效的数据同步功能 解决异构数据源同步问题 DataX

  • ElementUI中文官方文档

    组件 Element

  • day1 牛客TOP100：BM 1-10 链表

    文章目录 链表 BM1 反转链表 BM2 链表内指定区间反转 BM3 链表中的节点每k个一组翻转 BM4 合并两个排序的链表 BM5 合并k个已排序的链表 BM6 判断链表中是否有环 BM7 链表中环的入口结点 BM8 链表中倒数最后k个结

热门标签