【经典题目】链表OJ（轮转数组、返回倒数第k个节点、链表的回文结构）

小编主页详情-请点击小编gitee代码仓库-请点击本文主要介绍了有关链表的各种经典面试题目内容全由作者原创无AI同时深度解析了题目的经典解决方法并带有配图帮助博友们更好的理解点个关注不迷路下面进入正文~~目录1.轮转数组2.返回倒数第k个节点3.链表的回文结构结语1.轮转数组题目链接轮转数组方法1我们可以先保存数组的最后一个元素然后将前n-1个元素向后挪一位。将这些操作重复k次就能实现轮转数组。可当我们的K值比数组的元素还多的是时候会出现重复轮转的操作。拿示例1举个例子数组元素有7个那么当k3和k10时有区别吗显然没有区别。所以我们循环的次数可以是k%n次这样有利于提高程序的运行效率。那么当我提出这样的要求该怎么做呢你可以用空间复杂度为O(1)的原地算法解决这个问题吗方法2这是一个比较巧妙的方法名叫三段逆置。具体布置如下图所示。我们发现三段逆置后就刚好是正确答案。具体代码如下void reverse(int* nums, int n) { int left 0; int right n - 1; while(left right) { int tmp 0; tmp nums[left]; nums[left] nums[right]; nums[right] tmp; left; right--; } } void rotate(int* nums, int numsSize, int k) { int n numsSize; k k % n; reverse(nums,n); reverse(nums,k); reverse(nums k,n - k); }2.返回倒数第k个节点题目链接返回倒数第k个节点思路1先找出链表的长度减去k再遍历链表思路2逆置链表再数第k个节点思路3快慢指针。我们可以让快指针先走k步让快慢指针保持距离k当快指针指向NULL时慢指针刚好指向倒数第k个节点详细代码如下int kthToLast(struct ListNode* head, int k) { struct ListNode* fast head; struct ListNode* slow head; while(k--) { fast fast-next; } while(fast) { slow slow-next; fast fast-next; } return slow-val; }3.链表的回文结构题目链接链表的回文结构这道题目我们主要使用快慢指针和链表逆序的方法首先我们先使用快慢指针遍历一遍链表慢指针一次走一步快指针一次走两步。我们发现无论链表的节点是奇数还是偶数当快指针遍历完数组时慢指针刚好停在中间位置且这个位置又恰好是回文链表前半节的最后一个节点这个时候我们尝试将中间节点后面的链表倒转这里我们发现mid往后的节点其实和头节点往后的节点是重合的。这里需要额外注意虽然链表的后面逆置了但是mid的前一个节点的指向并没有改变这个节点仍然是指向他原来要指向的下一个节点。因此我们可以再头节点和mid的节点同时向后遍历如果出现数值不相同就说明这个链表不是回文链表。当头节点或mid节点走到NULL时说明已经遍历完了这个链表就是回文链表。下面是这道题目的完整代码/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: struct ListNode* reverseList(ListNode* head) { struct ListNode* cur head; struct ListNode* next NULL; struct ListNode* newnode NULL; while(cur) { next cur-next; //用next指针先保存下一个节点 cur-next newnode; //将当前节点的next指向新的头节点 newnode cur; //cur成为新的头节点 cur next; //将cur指向提前保存好的下一个节点 } //此时链表已经成功逆置newnode就我们需要的mid节点 return newnode; } bool chkPalindrome(ListNode* A) { // write code here struct ListNode* head A; struct ListNode* slow head; struct ListNode* fast head; while(fastfast-next) { slowslow-next; fastfast-next-next; } //此时slow就是中间节点 struct ListNode* mid reverseList(slow); while(head mid) { if(head-val!mid-val) { return false; } head head-next; mid mid-next; } return true; } };结语这篇文章全文由作者手写图片由画图软件所制无AI制作希望各位博友能有所收获欢迎各位博友的讨论觉得不错的小伙伴别忘了点赞关注哦~