【庖丁解牛:经典面试题之链表】

经典面试题之链表篇以下是我分享的一些经典面试题题解大家可以根据自己需要在目录中查找-----------------------------------------------------------------------------题目来源于力扣 点击展开/收起 文章目录文章目录经典面试题之链表篇1.查找链表中间节点2.合并两有序链表3.返回倒数第K个节点4.相交链表不卷会死星人肘击难点5.回文链表6.带环链表7.复杂链表的拷贝希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力1.查找链表中间节点方法提示:快慢指针法释义:就是设定一个快指针一次走两步,慢指针一次走一步,最后慢指针停下的位置就是中间节点结束条件:fast fast-next,此时直接返回慢指针即可typedefstructListNodeListNode;structListNode*middleNode(structListNode*head){ListNode*slow,*fast;slowfasthead;while(fastfast-next){fastfast-next-next;slowslow-next;}returnslow;}2.合并两有序链表可参考我第一篇顺序表篇最后合并两有序数组的思路区别:在处理时我们开辟一个新节点作为哨兵位,两链表互相比大小,较小的尾插到新链表之后,且在最后,有一个链表还有剩余元素,直接将其尾插到ptail后面即可typedefstructListNodeListNode;structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){ListNode*l1,*l2;l1list1;l2list2;ListNode*phead(ListNode*)malloc(sizeof(ListNode));ListNode*ptailphead;phead-nextNULL;while(l1l2){if(l1-vall2-val){ptail-nextl1;ptaill1;l1l1-next;}else{ptail-nextl2;ptaill2;l2l2-next;}}if(l1){ptail-nextl1;}else{ptail-nextl2;}returnphead-next;}3.返回倒数第K个节点*思路:*我们只需要两个指针,一个先走K步,然后一起走,等先走的那个指针走出链表,此时,后走的链表的位置就是倒数第K个位置typedefstructListNodeListNode;intkthToLast(structListNode*head,intk){ListNode*l1,*l2;l1l2head;while(k--){l2l2-next;}while(l2){l2l2-next;l1l1-next;}returnl1-val;}4.相交链表题目简述:给定两个单链表的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。思路:由于要判断并返回相交交点,首先明确,两个链表只要相交,不管交点在哪里,只要相交尾节点地址必然相同,那么只用两链表分别找尾比较尾节点地址判断是否相同即可判断是否相交,如何找交点?如图所示:我们只需要从相同位置开始走即可,那么就让长链表先走比短链表多出的部分再一起走因此在遍历链表找尾时我们用kA,kB记录两链表长度,在下面我们用到了一个函数abs(kA - kB);,abs就是用来计算kA-kB的绝对值来算出相对长度typedefstructListNodeListNode;structListNode*getIntersectionNode(structListNode*headA,structListNode*headB){ListNode*pcurA,*pcurB;pcurAheadA;pcurBheadB;intkA,kB;kAkB1;while(pcurA-next){pcurApcurA-next;kA;}while(pcurB-next){pcurBpcurB-next;kB;}if(pcurApcurB){ListNode*longList,*shortList;//注意这里我们用假设法来定义的长链表,短链表在下面用if语句判断调整longListheadA;shortListheadB;if(kAkB){shortListheadA;longListheadB;}intkabs(kA-kB);while(k--){longListlongList-next;}//两链表一起走找交点while(longList!shortList){longListlongList-next;shortListshortList-next;}returnshortList;}else{returnNULL;}}不卷会死星人肘击难点5.回文链表题目简述:如果一个链表是回文那么链表节点序列从前往后看和从后往前看是相同的,给定一个链表的 头节点 head 请判断其是否为回文链表。思路:我们的思路是先找中间节点,然后反置中间节点之后的节点话不多说,看图:在这里反置中间节点后的链表如图所示,我们只要从l3和head开始同时遍历链表val值prevhead,prev从头开始遍历,如果遍历完l3值都一直与prev值相等则就是回文问链表typedefstructListNodeListNode;boolisPalindrome(structListNode*head){ListNode*slow,*fast;slowfasthead;//找中间节点while(fastfast-next){fastfast-next-next;slowslow-next;}//链表反置,不会的可以去看看链表篇,里面有详细的讲解ListNode*l1,*l2,*l3;l1slow;l3l2NULL;while(l1){l2l1;l1l1-next;l2-nextl3;l3l2;}//prev,与l3遍历比较val值ListNode*prevhead;while(l3!NULL){if(l3-val!prev-val){returnfalse;}l3l3-next;prevprev-next;}returntrue;}6.带环链表题目简述:给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。思路:1.先判断有没有带环用快慢指针遍历链表如果带环fast,和slow就会相遇2.找入环口位置相遇之后设定一个meet指针从相遇位置开始走,另一个指针pcur从链表头开始走,pcur与meet相遇一起时该节点就是如环口我会在下图证明typedefstructListNodeListNode;structListNode*detectCycle(structListNode*head){ListNode*slow,*fast;slowfasthead;intpos-1;.//用来记录入环口节点位置ListNode*meetNULL;//快慢指针判断带环while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){meetfast;break;}}ListNode*pcurhead;if(meet){//找入环口记录入环口在第几个节点while(meet!pcur){meetmeet-next;pcurpcur-next;pos;}}if(pos-1){returnmeet;}else{returnpcur;}}7.复杂链表的拷贝题目简述:请实现 copyRandomList 函数复制一个复杂链表。在复杂链表中每个节点除了有一个 next 指针指向下一个节点还有一个 random 指针指向链表中的任意节点或者 null。思路:先复制链表,这里复制链表要用到特殊方法处理,把对应值复制在对应位置之后,再通过一些关系,找到random关系请看图如何将拷贝节点剪下来?直接遍历原链表找到原链表后的复制节点,尾插到pheadNode*copyRandomList(Node*head){if(headNULL){returnNULL;}//将对应值插入在原链表后面structNode*pcurhead;while(pcur){structNode*copy(structNode*)malloc(sizeof(Node));copy-nextpcur-next;pcur-nextcopy;copy-valpcur-val;pcurcopy-next;}pcurhead;structNode*copyNULL;//处理randomwhile(pcur){copypcur-next;if(pcur-randomNULL){copy-randomNULL;}else{copy-randompcur-random-next;}pcurcopy-next;}//将复制链表剪下来pcurhead;copyNULL;structNode*pheadNULL;structNode*ptailNULL;structNode*nextNULL;while(pcur){copypcur-next;nextcopy-next;if(pheadNULL){pheadptailcopy;}else{ptail-nextcopy;ptailcopy;}pcur-nextnext;//这一步是还原原链表pcurnext;}returnphead;希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力