天水模板型网站建设,电子商务静态网站建设心得,网站1g空间多大,做网站公司的使命#x1f4af;#x1f4af;#x1f4af;链表经典面试题❗❗❗炒鸡经典#xff0c;本篇带有图文解析#xff0c;建议动手刷几遍。#x1f7e5;1.反转链表#x1f7e7;2.合并两个有序链表#x1f7e8;3.链表分割#x1f7e9;4.链表的回文结构#x1f7e6;5.相交链表链表经典面试题❗❗❗炒鸡经典本篇带有图文解析建议动手刷几遍。1.反转链表2.合并两个有序链表3.链表分割4.链表的回文结构5.相交链表1.反转链表 方法一利用双指针逆转方向 将各个结点的连接方向都倒过来2结点指向1结点3结点指向2结点等我们只要将让每个结点的next指向前一个结点的地址
双指针–将指针指向前面最后一个变成头。两个指针一前一后 注意点
单链表不能往前走第一个指针首先指向NULL 第二个指针在后面这两个指针用来转变指向 不过这时第二个指针的后面的地址无法知道这时需要第三个指针用来记录第二个指针后面的结点的地址。当第三个指针往后走的时候可能为NULL要注意下
代码如下
struct ListNode* reverseList(struct ListNode* head)
{if(headNULL)//如果链表为空则直接返回NULLreturn NULL;struct ListNode* prev NULL;//与cur搭配记录前面的一开始为NULLstruct ListNode* cur head;//一开始为第一个结点所以将head传给cur让cur遍历链表struct ListNode* next cur-next;//next用来记录cur后面结点的地址while (cur)//当cur不为NULL时进行{//方向逆转cur-next prev;//将每一个结点的next指向前一个结点的地址//迭代--让我们的条件往后执行prev cur;//让pre跑到cur的位置上来cur next;//让cur跑到next的位置上来if (next)//这里next可能会跑着跑着为NULL了所以需要判断下next next-next;//往后跑}return prev;//最后尾就是头了将尾传回去
}方法2利用头插原理 取原结点头插到新链表 原本是1 2 3 4 5 我们只要将每个结点拿下来然后头插到一个新链表上就会变成5 4 3 2 1了
代码如下
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur head;//利用cur进行遍历不要用形参headstruct ListNode* newnode NULL;//首先创建一个新的空链表while (cur)//当cur为空时结束{//首先要记录下来cur后面结点的地址struct ListNode* next cur-next;//头插cur-next newnode;//将取下来的结点头插到新链表中newnode cur;//更新头指针cur next;//cur要往后走}return newnode;//返回新链表的头指针
}2.合并两个有序链表 这种题目在数组中也有类似的原理也是一样合并两个有序数组 也就是依次比较取小的结点尾插最后如果比较完还有结点直接尾插到没有结点的后面去。
注意点 当第一次尾插到一个新链表时我们需要的 是进行直接赋值将第一个结点直接赋值给新链表的头指针而不能进行尾插 当第一次以后才可以进行真正的尾插 当其中有一个或两个链表为空链表的话那么直接跳过比较环节而进入将还有结点的直接尾插到没有结点的后面去 这时因为没有结点的链表为NULL所以就无法访问它的next也就无法将它和另一个链表链接起来。 所以这时我们需要在前面讨论一下当其中有一个链表为NULL则直接返回另外一个链表。
方法1
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){if (list1 NULL)//当链表1为空则直接返回链表2return list2;if (list2 NULL)//当链表2为空则直接返回链表1return list1;struct ListNode* cur1 list1, * cur2 list2;//利用cur1cur2遍历链表struct ListNode* head NULL, * tail NULL;//head,用来传回tail用来找尾while (cur1 cur2)//当其中有一个结束就结束{if (cur1-val cur2-val)//哪个小就尾插谁{//将小的尾插//但一开始为空第一步就是赋值if (head NULL){head tail cur1;}//接下来才是真正的尾插else{tail-next cur1;//将cur1链接在tail的后面tail tail-next;//tail要往后找尾这样就不需要每次从开始进行找尾了}cur1 cur1-next;//cur往后走}else {//将小的尾插//但一开始为空第一步就是赋值if (head NULL){head tail cur2;}//接下来才是真正的尾插else{tail-next cur2;tail tail-next;}cur2 cur2-next;}}//将长的链表指针尾插到tail后面//不过还有一种情况就是plist为空cur1为空则tail还是NULL这种情况需要讨论if (cur1){tail-next cur1;}else{tail-next cur2;}return head;//返回head
}还有一种方法可以避免讨论tail的next是否为空和第一次尾插需要赋值等问题。 我们可以利用带有头哨兵卫的头结点。 这样tail永远不可能为空了就不需要讨论那么多为空的情况了。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* cur1 list1, * cur2 list2;struct ListNode* head NULL,* tail NULL;struct ListNode* guard tail (struct ListNode*)malloc(sizeof(struct ListNode));//动态开辟一个哨兵头结点让tail一开始就指向头结点这样tail就永远不会为NULL了while (cur1 cur2)//当其中有i一个结束就结束{if (cur1-val cur2-val){//将小的尾插//不需要进行讨论第一个头节点为NULL的情况了直接进行尾插tail-next cur1;tail tail-next;cur1 cur1-next;}else{//将小的尾插tail-next cur2;tail tail-next;cur2 cur2-next;}}//将长的链表指针尾插到tail后面//如果没有哨兵头plist为空cur1为空则tail还是NULL这种情况就需要讨论//但先走有了哨兵头结点tail不可能为空直接让tail的next与另一个链表剩余的结点链接起来if (cur1){tail-next cur1;}else{tail-next cur2;}headguard-next;//将第一个结点的地址记录下来free(guard);//释放guardreturn head;
}3.链表分割 要求将所有小于x的结点排在其他结点之前且不能改变原来的数据顺序 我们可以这样做
将小于x的结点插入到一个链表中将大于x的结点插入到一个链表中最后将两个链表链接起来。 不过这里我们最好使用带有哨兵头的链表这样可以减少进行对NULL的讨论不然会很麻烦 比如如果数据全是 6 6 6 6 6 而x为5 则less链表为空那么将两个链表链接起来有会出问题ltail都为NULL还有next吗所以我们使用带有哨兵卫的链表能很好的减少这种讨论。
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode* Lguard,*Gguard,*ltail,*gtail;Lguardltail(ListNode*)malloc(sizeof(ListNode));//less链表的哨兵头Gguardgtail(ListNode*)malloc(sizeof(ListNode));//greater链表的哨兵头ltail-nextNULL;//一开始要置NULLgtail-nextNULL;ListNode* curpHead;//利用cur进行遍历while(cur){if(cur-valx)//如果小于x就尾插到less的链表中{ltail-nextcur;//将小的数据尾插到ltail的后面ltailltail-next;//找尾}else {gtail-nextcur;//将大的数据尾插到gtail后面gtailgtail-next;}curcur-next;//每次cur也要往后走}ltail-nextGguard-next;//让两个链表链接起来gtail-nextNULL;//想一想这一步是为什么呢因为最后7的next还链接着2呀这样就造成回环了。所以需要将gtail的next置为NULLpHeadLguard-next;//第一个结点free(Lguard);//释放free(Gguard);//释放return pHead;//返回第一个结点地址}
};4.链表的回文结构 我们看到链表时有时就会想转空子想先使用数组来存储链表的数据然后再进行判断我们在知道链表长度的前提下理论上是可以的但最好不要这样做如果不知道长度我们还需要动态增容等所以要抛弃这个想法。 那怎么判断回文结构呢 回文结构也就是对称从中间对称左边与右边对称如果我们把右边逆转下那么右边就和左边一样了。所以我们就可以根据左边和右边是否一样进行判断了
首先我们需要找到中间结点逆转中间结点以后的结点从逆转开始的位置与开头进行比较
逆转链表查找链表的中间结点我都已经写过了这里直接就复制过来。 《找链表的中间结点》 《反转链表》
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)//找链表中间结点
{struct ListNode *fast,*slow;fastslowhead;while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;}return slow;}
struct ListNode* reverseList(struct ListNode* head)//反转链表
{
struct ListNode* cur head;struct ListNode* newnode NULL;while (cur){//首先要记录下来cur后面结点的地址struct ListNode* next cur-next;//头插cur-next newnode;newnode cur;//更新头指针cur next;//cur要往后走}return newnode;
}bool chkPalindrome(ListNode* phead){ListNode *mid middleNode(phead);//找中间结点ListNode *rhead reverseList(mid);//逆转中间结点以后//比较链表前面数据与逆转后的数据while(rhead)//当逆转后的结点走到NULL时结束{if(rhead-val!phead-val)return false;//当有一个不等于就然后falsepheadphead-next;rheadrhead-next;}return true;//走到这说明都相等}
};5.相交链表 怎么判断两个链表是否相交呢 怎么返回这个相交结点呢
传统思想可能会让链表A中每个结点的地址与链表B中结点的地址都比较一下当第一次比较相同时就是相交结点不过这种方法的时间复杂度为O(N^2)了不好有没有让时间复杂度为O(N)的呢
好的让我来告诉你吧 如果两个链表是相交的那么它们的尾结点的地址一定相同如果尾结点地址不相同那么肯定不相交。 接着让长的链表先走长度差步然后两个链表再一起走当两个链表结点地址比较相同时就是相同结点的位置。 所以
求出两个链表的长度判断是否相交。让长度长的链表先走长度差步然后一起走两个链表结点地址相比第一次相同的为相交结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *cur1headA,*cur2headB;//用cur1遍历链表A用cur2遍历链表2int lena0;int lenb0;while(cur1-next)//记录链表A的长度{cur1cur1-next;lena;}while(cur2-next)//记录链表B的长度{cur2cur2-next;lenb;}if(cur1!cur2)//如果链表尾结点不相同那么肯定不相交return NULL;int gapabs(lena-lenb);//长度差但我们不知道哪个链表长struct ListNode *longlistheadA,*shortlistheadB;if(lenblena)//所以我们需要讨论下{longlistheadB,shortlistheadA;}while(gap--)//让长的链表先走长度差步{longlistlonglist-next;}while(longlist!shortlist)//然后两个链表一起走当没有结点地址相同时则一起走{longlistlonglist-next;shortlistshortlist-next;}return longlist;//最后如果有相同的就返回
}
