黑群晖做网站,河北网站建设,网络推广平台推荐,档案网站的建设方案目录
一、前言
二、题目描述
三、解题方法 ⭐ 头插法 --- 创建新的链表 ⭐ 迭代法 --- 三指针 ⭐ 递归法
四、总结与提炼
五、共勉 一、前言 反转链表这道题#xff0c;可以说是--链表专题--#xff0c;最经典的一道题#xff0c;也是在面试中频率最高的一道题目…目录
一、前言
二、题目描述
三、解题方法 ⭐ 头插法 --- 创建新的链表 ⭐ 迭代法 --- 三指针 ⭐ 递归法
四、总结与提炼
五、共勉 一、前言 反转链表这道题可以说是--链表专题--最经典的一道题也是在面试中频率最高的一道题目通常在面试中面试官可能会要求我们写出多种解法来实现这道题目所以大家需要对这道题目非常熟悉哦 本片博客就来详细的讲讲解一下 反转链表的多种实现方法让我们的面试变的更加顺利 二、题目描述 给你 单链表 的头节点 head 请你反转链表并返回反转后的链表。 三、解题方法 ⭐ 头插法 --- 创建新的链表 头插这种方法就是将结点一一地插入到新链表的头前所以我们需要先去建立出一个新的链表头也就是我下面的这个【rhead】通过去遍历原先的链表将这些结点一一转移过去即可 定义三个 变量 cur 、newnode 、rhead cur 用于遍历整个旧链表 newnode 用于记录cur的下一个节点防止旧链表找不到rhead 新链表的头节点
// 重新创建一个链表将之前的链表进行头插即可
struct ListNode* rphead NULL;
// 进行指针变换
struct ListNode* cur head; 开始头插cur 节点的 next 指向 rhead 节点然后更新 rhead 、cur 、newnode 这三个节点 // 用于保存下一个节点地址struct ListNode* newnode cur-next;// 头插cur-next rphead;rphead cur;cur newnode; 继续同样的操作 此时当【cur NULL】时便结束一个遍历然后新链表的头就是【rhead】返回即可 完整代码
struct ListNode* reverseList(struct ListNode* head)
{// 重新创建一个链表将之前的链表进行头插即可struct ListNode* rphead nullptr;// 进行指针变换struct ListNode* cur head;while(cur!NULL){// 用于保存下一个节点地址struct ListNode* newnode cur-next;// 头插cur-next rphead;rphead cur;cur newnode;}return rphead;
} ⭐ 迭代法 --- 三指针 三指针的迭代方法这种方法不需要在去创建一个新的头结点指针只需要在原先的链表上进行一个操作即可也就是定义三个指针。 cur指向当前链表的头nextnode指向cur的next一样是用于保存。prev这个的话其实是用来算作链表最后一个结点指向空的。 ListNode* prev nullptr;
ListNode* cur head;
ListNode* nextNode cur-next;然后将【cur-next prev】让原本的头【cur】作为反转后新链表的尾巴 接着就是进行的一个迭代操作首先将【cur】当前的值给到【prev】然后将【nextnode】当前的值给到【cur】然后让【nextnode】继续向下这个时候其实就进行了一个迭代的操作 cur-next prev;
prev cur;
cur nextnode;
然后继续做翻转让【cur-next】指向 prev, 并更新三个指针 可以看到当这个【cur NULL】时整个链表便完成了一个翻转此时便结束循环迭代的逻辑 然后可以看到此时新链表的头并不是【cur】而是【prev】所以最后应该返回【prev】 完整代码
class Solution {
public:ListNode* reverseList(ListNode* head) {// 1. 迭代法// 定义三个指针ListNode* prev nullptr; // cur 的前一个节点ListNode* cur head;// 开始迭代while(cur!nullptr){ListNode* nextnode cur-next; // cur的下一个指针cur-next prev;prev cur;cur nextnode;}return prev;}
}; ⭐ 递归法 我们可以通过迭代的方法来得到递归方法 函数声明中 prev 指针指向的为 NULLcur 指针指向的为 head正如递归中声明并初始化的prev 和 cur 指针递归结束条件为 cur 为 NULL, 返回 prev同样 newnode 保存 cur 的下一个节点以防止反转时丢失链表信息。然后进行反转 cur-next prev;prev为当前已反转部分的头节点cur为当前待反转的节点。然后调用递归将cur作为新的 prev 传入下一层将 newnode 作为新的 cur 传入下一层。实现了链表的递归反转
class Solution {
public:ListNode* reverse(ListNode* prev, ListNode* cur){// 最终结束条件if(curnullptr){return prev;}ListNode* newnode cur-next;cur-next prev;// 将 cur 作为 prev 传入下一层// 将 newnode 作为 cur 传入下一层改变其指针指向当前 curreturn reverse(cur,newnode);}ListNode* reverseList(ListNode* head) {// 3. 递归法return reverse(nullptr,head);}
}; 四、总结与提炼 最后我们来总结一下本文所介绍的内容本文讲解来一道力扣中有关链表翻转的题目这道题目是校招笔试面试中有关链表章节非常高频的一道题目大家下去一定要自己再画画图分析一下把这段代码逻辑自己实现一遍才能更好地掌握 五、共勉 以下就是我对 反转链表 的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对 链表专题 的理解请持续关注我哦
