免费做网站平台,十大最免费软件排行榜,企业宣传片制作价格,小程序装修页面设计hi#xff0c;bro—— 目录
5、 链表分割
6、 链表的回文结构
7、 相交链表
8、 环形链表
【思考】 —————————————— DEAD POOL —————————————— 5、 链表分割 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), …hibro—— 目录
5、 链表分割
6、 链表的回文结构
7、 相交链表
8、 环形链表
【思考】 —————————————— DEAD POOL —————————————— 5、 链表分割 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include functional
class Partition {
public:ListNode* partition(ListNode* pHead, int x){//创建新的大小链表ListNode* lessHead,*lessTail;lessHeadlessTail(ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead,*greaterTail;greaterHeadgreaterTail(ListNode*)malloc(sizeof(ListNode));//创建新的头结点遍历数组ListNode* pcurpHead;while(pcur){if(pcur-valx){//尾插到小链表lessTail-nextpcur;lessTaillessTail-next;}else{//尾插到大链表greaterTail-nextpcur;greaterTailgreaterTail-next;}pcurpcur-next;}//大小链表首尾相连lessTail-nextgreaterHead-next;greaterTail-nextNULL;ListNode* retlessHead-next;free(lessHead);free(greaterHead);lessHeadNULL;greaterHeadNULL;return ret;}
}; 6、 链表的回文结构 在链表中不可回找但是数组可以回找所以我们可以把链表中的数据放到数组中。
思路1创建新数组遍历原链表将链表中的值放到数组中然后在数组中判断是否为回文结构。
因为题目中提前对链表的长度进行了限制若不限制空间复杂度为ON就不符合题目的条件了
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {int arr[900]{0};ListNode* pcurA;int i0;//将链表中的数据赋给数组while(pcur){arr[i]pcur-val;pcurpcur-next;}//i为链表中结点的个数//判断数组中的值是否为回文结构int left0;int righti-1;while(leftright){if(arr[left]!arr[right]){return false;}left;right--;}return true;}
}; 思路2反转链表这种方法的时间复杂度为ON空间复杂度为O1
1找原链表的中间结点“快慢指针”
2将中间结点及之后的结点进行反转
3从原链表的头结点和新链表的头结点开始遍历比较。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://找中间结点ListNode* findMidNode(ListNode* phead){ListNode* slow,*fast;slowfastphead;while(fastfast-next){slowslow-next;fastfast-next-next;}return slow;}//反转链表ListNode* reverseList(ListNode* phead){ListNode* n1,*n2,*n3;n1NULL;n2phead;n3n2-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}return n1;}bool chkPalindrome(ListNode* A) {//1.找中间结点ListNode* midfindMidNode(A);//2.反转链表ListNode* rightreverseList(mid);//3.遍历比较ListNode* leftA;while(right){if(left-val!right-val)return false;leftleft-next;rightright-next;}return true;}
}; 7、 相交链表 思路1判断两个链表是否相等 2返回两个单链表相交的起始结点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* l1headA;ListNode* l2headB;int countA0;int countB0;//求两个链表的长度while(l1){countA;l1l1-next;}while(l2){l2l2-next;countB;}//求链表长度差值的绝对值int gapabs(countA-countB);//判断哪个是长短链表ListNode* longListheadA;ListNode* shortListheadB;if(countAcountB){longListheadB;shortListheadA; }//让两个链表在同一起跑线while(gap--){longListlongList-next;}//判断两个链表是否相交while(longListshortList){//相交if(longListshortList){return longList;}longListlongList-next;shortListshortList-next;}//不相交return NULL;
} 8、 环形链表 思路 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slowhead;ListNode* fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;
} 【思考】
头好痒感觉要长脑子了 完—— Relaxing Time ! —————————————— DEAD POOL —————————————— https://t3.kugou.com/song.html?idc35Fp66CPV2https://t3.kugou.com/song.html?idc35Fp66CPV2 能力越大越没责任 Bye ~~~
