网站开发课题开发背景,工程承包app,上海工程建设信息网站,dw做网站如何让用户可编辑一、链表分割
牛客网链接
题目描述#xff1a;
现有一链表的头指针 ListNode* pHead#xff0c;给一定值x#xff0c;编写一段代码将所有小于x的结点排在其余结点之前#xff0c;且不能改变原来的数据顺序#xff0c;返回重新排列后的链表的头指针。
思路#xff1a;…一、链表分割
牛客网链接
题目描述
现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。
思路
题目中要求不能改变原来的数据顺序所以不能采用交换的方法写应该单独创建两个链表第一个链表尾插小于x的数据另外一条链表尾插大于x的数据最后将这两条链表进行链接。
尾插不改变原来数据顺序头插将原来的数据顺序逆置。
我们引用哨兵卫头结点解决这道题会更加方便。
不仅方便尾插不需要分类判断空指针与否而且也避免两个链表链接时第一个链表为空的情况。 TIP
一般尾插时最后一个结点的next容易出现问题我们一般需要自己将其置成空指针 代码
#include cstddef
#include cstdlib
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* ghead,*gtail,*lhead,*ltail;//使用哨兵卫的头结点更加简单gheadgtail(struct ListNode*)malloc(sizeof(struct ListNode));lheadltail(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* curpHead;while(cur){if(cur-val x){ltail-nextcur;ltailltail-next;}else {gtail-nextcur;gtailgtail-next;}curcur-next;}gtail-nextNULL;//滞空不然可能导致环形链表的出现ltail-nextghead-next;struct ListNode* newheadlhead-next;free(ghead);free(lhead);return newhead;}
};
二、链表的回文结构
牛客网链接
题目描述
对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。
给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。
测试样例
1-2-2-1
返回true
思路
因为单链表只能从一个方向开始遍历所以先让一串链表从中间结点开始往后逆置接着两端链表进行比较。从中间结点开始逆置需要找中间结点逆置也是之前讲过的相当于再次复习巩固一遍
代码
#include cstddef
class PalindromeList {
public:bool chkPalindrome(ListNode* head) {//寻找中间结点struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}//从中间结点开始逆置struct ListNode* newheadNULL;struct ListNode* curslow;struct ListNode* nextNULL;while(cur){nextcur-next;cur-nextnewhead;newheadcur;curnext;}//开始判断while(head newhead){if(head-val!newhead-val){return false;}headhead-next;newheadnewhead-next;}return true;}
};
三、相交链表
leetcode链接
题目描述
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
思路
首先有一个暴力解法从第一条链表开始将每一个结点的地址与第二条链表比较直到找到相同的为止这样的时间复杂度就是O(N^2)不太理想下面将一个O(N)的算法
首先判断有无相交结点直接遍历两条链表看尾结点的地址是否相同。
如果相同则计算两条链表的结点的差值接着让长的链表先走差值步这时因为相交结点后面的个数一定相同长的链表走差值步后相交结点的前面也是相同个数的结点直接一一比较地址是否相同就不用遍历两遍了也就是O(N)。
代码
truct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curAheadA;struct ListNode* curBheadB;int numA1;int numB1;//判断是否有相交的结点while(curA-next){curAcurA-next;numA;}while(curB-next){curBcurB-next;numB;}if(curA!curB){return NULL;}int gapabs(numA-numB);//直接假设长链表不用if语句struct ListNode* longlistheadA;struct ListNode* shortlistheadB;if(numAnumB){longlistheadB;shortlistheadA;}//长的先走差距步,走gap步就是后置--while(gap--){longlistlonglist-next;}//在已知有公共结点的情况下遍历返回while(1){if(longlistshortlist){return longlist;}longlistlonglist-next;shortlistshortlist-next;}
}
四、环形链表
leetcode链接
题目描述
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。 思路
本题要求较为简单只需要判断是否含有环形结构我们还是利用快慢指针的思想快指针走两步慢指针走一步如果不带环则快指针作为循环判断的条件如果带环则最后两者肯定会相遇直到快慢指针地址相同时跳出循环。
代码
bool hasCycle(struct ListNode *head)
{struct ListNode* slowhead;struct ListNode* fasthead;while(fast fast-next){slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;
}
五、环形链表进阶
142. 环形链表 II - 力扣LeetCode
题目描述
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
思路一
本题主要找环形链表进入环的第一个节点当然需要判断是不是环形链表判断后需要进行一个数学的函数证明 经过计算验证我们发现一个指针从起点走另外一个从相遇点走在相同步伐下他们会在入口点相遇
有这样一个等式接下来就只需要找相遇点正好上一题我们就找的是相遇点。
代码
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow head;struct ListNode* fast head;struct ListNode* meet NULL;struct ListNode* cur head;//先判断是否有环while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){//找到相遇结点meet slow;break;}}if(meetNULL){return NULL;}//相遇节点与头结点一起走直到相等就是入口while(1){if(meetcur){return meet;}meetmeet-next;curcur-next;}
}
思路二
利用相交链表的思路。
首先也是找到相遇点然后将相遇点的后面的结点断掉这样就形成了两个链表一条链表从头结点开始另一条链表从断口开始。并且这两个链表的交点就是我们的入口点 struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode* slow head;struct ListNode* fast head;struct ListNode* meet NULL;struct ListNode* cur head;//先判断是否有环while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){//找到相遇结点meet slow;break;}}if(meetNULL){return NULL;}//struct ListNode* newhead meet-next;meet-next NULL;struct ListNode* curnew newhead;//开始相交链表int len1 0;int len2 0;while(curnew){curnewcurnew-next;len1;}while(cur){curcur-next;len2;}int gapabs(len1-len2);struct ListNode* longlist newhead;struct ListNode* shortlist head;if(len1len2){longlist head;shortlistnewhead;}while(gap--){longlistlonglist-next;}while(1){if(longlistshortlist){return longlist;}longlistlonglist-next;shortlistshortlist-next;}}
