wordpress更改站点地址,国家城乡住房建设部网站首页,成都装饰公司前十强是哪几个,网页的后缀名有那些文章目录前言链表的中间结点链表中倒数第k个结点写在最后前言 对于单链表的OJ练习#xff0c;需要深刻理解做题的思路#xff0c;这样我们才能够在任何场景都能够熟练的解答有关链表的问题。 关于OJ练习#xff08;1#xff09;#xff1a;- 传送门 -#xff0c…
文章目录前言链表的中间结点链表中倒数第k个结点写在最后前言 对于单链表的OJ练习需要深刻理解做题的思路这样我们才能够在任何场景都能够熟练的解答有关链表的问题。 关于OJ练习1- 传送门 -其题目较为简单思路也好理解本章与1差不多难度不大核心点就在于理解解题思路。 链表的中间结点
题目链接- 传送门 -。
该题目描述为给你单链表的头结点 head 请你找出并返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。
1.如果节点数为奇数这个中间节点就显而易见了。3
2.如果节点数为偶数这里认为中间两个节点的第二个节点为中间节点。4
思路一 我们可以先遍历一遍链表统计一下链表节点的个数。 然后将这个个数除以二加一count / 2 1便是中间这个节点的位置。 当然我们在循环寻找这个中间节点的时候是从头节点开始的因此循环只需要循环count / 2 1 - 1即可。
代码实现
struct ListNode* middleNode(struct ListNode* head){struct ListNode* cur head;int count 0;while (cur){count ;cur cur-next;}count count / 2 1;while (-- count) // 循环count - 1次{head head-next;}return head;
}思路二 该做法为快慢指针。 啥为快慢指针呢在本题有关当中我们定义两个指针指向链表的头节点并且共同遍历链表不同的是一个指针每一次走两步另一个指针每次走一步这就是快慢指针。 每当快指针满足循环结束条件慢指针都是指向链表的中间节点的。因为快指针走两步慢指针走一步整个移动的位移差相差一倍所以每当快指针满足结束条件的时候慢指针走的步数都是快指针走的步数的一半 因此慢指针指向的那个节点就是整个链表的中间节点。 快指针结束的条件有两种情况一种是快指针刚好指向空结束一种是快指针指向尾节点结束也就是快指针的next为NULL。
1.当快指针刚好指向NULL结束此时链表的节点个数为偶数 2.当快指针指向尾节点结束也就是快指针的next为NULL此时链表的节点个数为奇数 代码实现
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast head, * slow head;while (fast fast-next){fast fast-next-next;slow slow-next;}return slow;
}注意 while循环的判断条件fast一定要在前面这是因为判断是从左到右判断的如果fast-next在前而此时链表的结点的个数为偶数那么fast就会直接到达NULL这时候对空指针解引用操作就出问题了。 链表中倒数第k个结点
题目链接- 传送门 -。
该题目描述为输入一个链表输出该链表中倒数第k个结点。。 思路一 既然是倒数第k个那我们就看看是正数的第几个。 先遍历一遍单链表统计一下链表的结点个数count通过数学知识可得倒数的第k个结点就是正数的第count - k 1个节点这时只要在遍历一次链表找到第count - k 1个节点返回即可。 当然这里嘚注意k是不是大于链表节点的个数的情况。
代码实现
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* cur pListHead;int count 0;// 统计链表节点的个数while (cur){count ;cur cur-next;}// 如果k大于链表的节点个数直接返回NULLif (k count) return NULL;int tmp count - k;// 由于从头个节点开始算因此只需要循环count - k次就可以找到倒数第k个节点while (tmp -- ){pListHead pListHead-next;}return pListHead;
}思路二
同样是快慢指针这里的快慢指针解法是快指针先向后走k步或者先向后走k - 1步然后快指针与慢指针同时向后走当快指针满足循环结束条件停止此时慢指针指向的节点就是倒数第k个节点。
1.如果快指针先向后走k步此时快指针与慢指针之间相差k步因此当快指针到达NULL时此时慢指针刚好指向倒数第k个节点。倒数第k个节点与NULL相差k步(循环结束条件fast NULL) 2.如果快指针先向后走k - 1步此时快指针与慢指针之间相差k - 1步然后快指针与慢指针同时向后走当快指针满足循环结束条件停止此时慢指针指向的节点就是倒数第k个节点。倒数第k个节点与尾节点相差k - 1步循环结束条件fast-next NULL 代码实现(这里只实现fast先走k步的情况fast先走k - 1的情况大同小异)
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow pListHead, * fast pListHead;// fast先走k步while (k -- ){if (!fast) return NULL; // 如果k还没为0但fast已经指向空了说明k大于链表的结点的个数此时直接返回NULLfast fast-next;}// 当fast为NULL时结束循环while (fast){fast fast-next;slow slow-next;}return slow;
}写在最后 对于单链表的题目练习最重要的是思路我们在数据结构阶段要养成画图的习惯因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。 感谢阅读本小白的博客错误的地方请严厉指出噢
