古典风格网站模板,做外贸要自己建网站吗,tp框架做餐饮网站,山西建工网登录文章目录 一、链表分割二、相交链表三、环形链表I四、环形链表|| 一、链表分割
题目链接#xff1a;https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70 我们来看看链表分割的题目描述和它给出的函数#xff1a; 这个题虽然是以C形式来做#xff0… 文章目录 一、链表分割二、相交链表三、环形链表I四、环形链表|| 一、链表分割
题目链接https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70 我们来看看链表分割的题目描述和它给出的函数 这个题虽然是以C形式来做但是不用担心我们知道在哪里写代码就可以了就是题目提示的地方这个属于C类的知识我们在后面的C部分会详细介绍 接着我们回归正题题目要求我们将链表分割开来值小于x的节点要放在链表的左边值大于等于x的节点要放在链表的右边这个题该怎么做呢 方法和双指针的算法有点类似但是又不完全相同我们可以创建两个新链表一个存放比x小的节点另一个存放比x大或者和x相等的节点最后让小链表和大链表首位相连即可 这里我们要注意的是如果我们创建的两个链表初始为空会发生什么我们每次插入节点时都要判断要插入的链表是否为空空和非空的操作不一致加上我们有两个新链表操作起来更加的繁琐 所以我们还是用上之前学过的知识怎么保证一个链表默认不为空没错就是在初始情况下创建一个哨兵位节点占位它不存放有效的数据单纯用来占位这样我们在插入节点时就不需要去判断链表是否为空了 最后我们再来大致梳理一下解题思路就是创建大小链表同时创建哨兵位占位然后遍历原链表把值小于x的节点放在小链表其它的放在大链表最后让小链表和大链表首尾相连即可题解如下
ListNode* partition(ListNode* pHead, int x) {ListNode* lesshead, *lesstail;ListNode* greaterhead, *greatertail;lesshead lesstail (ListNode*)malloc(sizeof(ListNode));greaterhead greatertail (ListNode*)malloc(sizeof(ListNode));ListNode* pcur pHead;while(pcur){if(pcur-val x){lesstail-next pcur;lesstail pcur;}else {greatertail-next pcur;greatertail pcur; }pcur pcur-next;}//小链表的尾巴连接大链表的头//大链表哨兵位的下一个节点是真正的头lesstail-next greaterhead-next;//为了避免形成环把尾节点的next指针置为空greatertail-next NULL;//要返回的头就是小链表哨兵位后真正的头ListNode* ret lesshead-next;//资源清理工作free(lesshead);free(greaterhead);lesshead NULL;greaterhead NULL;return ret;}我们提交一下试试
二、相交链表
题目链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 我们来看看题目描述和给出的函数 题目的要求就是给我们两个链表然后让我们判断这两个链表是否相交如果相交就返回相交的节点否则就返回空 我们要注意到相交链表的特殊性直线相交的话它们还会朝着不同的方向继续延伸想象一下链表相交以后会怎么样它们相交后一定只有一个方向而不会像直线相交那样有多个方向因为如果它们相交那么相交节点的next指针指向同一个节点如此循环下去自然就只有一个方向 那么问题好像要简单一些了我们遍历两个链表看看有没有相同的节点不就好了可是还是有一个问题我们看看题目的第一个示例就知道了 这个问题就是两个链表的长度可能不同在上面的示例中如果同时开始遍历的话当链表A遍历到相交节点8时链表B才遍历到节点1这样它们差一位就永远不能相等也就找不到相交节点 那有没有什么办法让它们从同一起跑线出发呢我们能让小的那个链表变长但是可以让大链表往前走两步呀比如上图我们就可以让大链表先往前走一步到6节点然后它们在同一起跑线往后遍历就可以找到相交节点了 问题是我们要怎么知道那个链表大大多少知道了这两个条件后我们就可以让大链表提前走它们的长度差距然后同时对他们进行遍历为了知道它们的大小我们可以定义两个整型计数器来计算它们的大小 然后根据大小来判断谁大谁小然后让大链表往前走它们的长度差距最后让大小链表同时往前遍历如果遇到相同的节点说明它们相遇了返回这个节点就可以了但是如果遍历到尾结点后还没有相同的节点说明两个链表不相交返回空题解如下
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{//创建两个节点指针遍历链表ListNode* pcurA headA;ListNode* pcurB headB;int countA 0, countB 0;while(pcurA){countA;pcurA pcurA-next;}while(pcurB){countB;pcurB pcurB-next;}//假设法来判断链表大小//假设A链表更小//如果假设错误后面计算出大小后进行修改ListNode* lesslist headA;ListNode* greaterlist headB;//如果A的节点个数大于B那么进行修改if(countA countB){lesslist headB;greaterlist headA;}//接着让大的链表往后走间隔大小//首先使用绝对值函数求间隔大小int size abs(countA - countB);while(size--){greaterlist greaterlist-next;}//此时两个链表在同一起跑线长度一样//然后再往后遍历while(lesslist){if(lesslist greaterlist){return lesslist;}lesslist lesslist-next;greaterlist greaterlist-next;}//出了循环说明没有相交返回NULLreturn NULL;
}最后提交一下代码
三、环形链表I
题目链接https://leetcode.cn/problems/linked-list-cycle/description/ 我们来看看环形链表I的题目描述与示例 我们首先要知道链表带环是什么意思就是它的尾结点的next指针不指向空了而是指向链表中的某个节点以此成为带环链表 这个题还较为简单只需要我们判断链表是否有环而不需要我们找出入环节点做这个题需要用到一个结论这里我就直接说出来了如果对它的证明过程感兴趣可以自行去了解一下当然也可以私信我我会及时给出解答这里就不多证明了 在这里我们需要用到快慢指针结论就是慢指针一次走一步快指针一次走两步如果链表带环那么快指针和慢指针一定会在环内相遇如果不带环那么循环直接结束了有了这个结论我们写起来就简单多了如下
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{ListNode* slow head;ListNode* fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){return true;}}return false;
}我们提交代码试试
四、环形链表||
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/description/ 我们来看看环形链表II的题目描述和示例 这个题和上一个题的最大区别就是这个题不仅要求我们判断链表是否是一个带环链表如果带环还要我们找出入环的第一个节点这个就比较难了 这里我们还是使用一个结论相关的证明可以自行了解也可以私信我我会及时给出解答这里就不多证明了 结论还是需要用到快慢指针如果链表带环那么快慢指针一定就会在环内相遇并且相遇节点到入环节点的距离和头结点到入环节点的距离相等 通俗一点说就是当快慢指针在环内相遇后让头结点和慢指针同时往前并且每次走一步那么当头结点和慢指针相遇时相遇节点就是入环节点 因为此时头结点和慢指针走的步数相同还相遇了根据上面的结论就可以说明相遇节点就是入环节点是不是特别神奇接着我们就根据这个结论来写代码如下
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head)
{ListNode* slow head;ListNode* fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){//进入这里说明链表带环ListNode* pcur head;while(pcur){//判断是否相等//不相等循环的往前走if(pcur slow){return pcur;}pcur pcur-next;slow slow-next;}}}//出了循环说明链表不带环return NULL;
}提交代码 那么今天的刷题分享就到这里啦如果有什么疑问欢迎提出题目中使用的相关证明也可以直接问我 最后感谢大家的观看bye~
